Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Mehlhorn, Kurt

dblp



BibTeX cite key*:

mehlhorn79j

Title

Title*:

Some Remarks on Boolean Sums


Mehlhorn_a_1979_j.pdf (198.01 KB)

Journal

Journal Title*:

Acta Informatica

Journal's URL:


Download URL
for the article:

http://www.springerlink.com/content/n834547372l98h74/fulltext.pdf

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

12

Number:


Publishing Date:

1979

Pages*:

371-375

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

Summary  Neciporuk, Lamagna/Savage and Tarjan determined the monotone network complexity of a set of Boolean sums if any two sums have at most one variable in common. Wegener then solved the case that any two sums have at most k variables in common. We extend his methods and results and consider the case that any set of h +1 distinct sums have at most k variables in common. We use our general results to explicitly construct a set of n Boolean sums over n variables whose monotone complexity is of order n 5/3. The best previously known bound was of order n 3/2. Related results were obtained independently by Pippenger.
This paper was presented at the MFCS 79 Symposium, Olomouc, Sept. 79

URL for the Abstract:

http://www.springerlink.com/content/n834547372l98h74/

Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{mehlhorn79j,
AUTHOR = {Mehlhorn, Kurt},
TITLE = {Some Remarks on {Boolean} Sums},
JOURNAL = {Acta Informatica},
PUBLISHER = {Springer},
YEAR = {1979},
VOLUME = {12},
PAGES = {371--375},
}


Entry last modified by Christine Kiesel, 01/05/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel
Created
08/07/2006 06:06:17 AM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
05.01.2007 14:06:26
04.01.2007 16:15:46
04.01.2007 16:08:33
07.08.2006 06:07:16
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_a_1979_j.pdf
View attachments here: