Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








Author, Editor

Author(s):

Lotker, Zvi
Majumdar, Debapriyo
Narayanaswamy, N.S.
Weber, Ingmar

dblp
dblp
dblp
dblp

Not MPG Author(s):

Lotker, Zvi
Narayanaswamy, N.S.

Editor(s):

Chen, Danny Z.
Lee, D. T.

dblp
dblp

Not MPII Editor(s):

Chen, Danny Z.
Lee, D. T.

BibTeX cite key*:

lotkeretal06cocoon

Title, Booktitle

Title*:

Sequences Characterizing k-Trees

Booktitle*:

Computing and Combinatorics, 12th Annual International Conference, COCOON 2006

Event, URLs

URL of the conference:

http://www.iis.sinica.edu.tw/cocoon06/

URL for downloading the paper:

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

Event Address*:

Taipei, Taiwan

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

9 June 2006

Event End Date:

9 June 2006

Publisher

Name*:

Springer

URL:


Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

4112

Number:


Month:


Pages:

216-225

Year*:

2006

VG Wort Pages:


ISBN/ISSN:

3-540-36925-2

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:


A non-decreasing sequence of n integers is the degree sequence of a 1-tree (i.e., an ordinary tree) on n vertices if and only if there are least two 1’s in the sequence, and the sum of the elements is 2(n–1). We generalize this result in the following ways. First, a natural generalization of this statement is a necessary condition for k-trees, and we show that it is not sufficient for any k > 1. Second, we identify non-trivial sufficient conditions for the degree sequences of 2-trees. We also show that these sufficient conditions are almost necessary using bounds on the partition function p(n) and probabilistic methods. Third, we generalize the characterization of degrees of 1-trees in an elegant and counter-intuitive way to yield integer sequences that characterize k-trees, for all k.

URL for the Abstract:

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



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

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



BibTeX Entry:

@INPROCEEDINGS{lotkeretal06cocoon,
AUTHOR = {Lotker, Zvi and Majumdar, Debapriyo and Narayanaswamy, N.S. and Weber, Ingmar},
EDITOR = {Chen, Danny Z. and Lee, D. T.},
TITLE = {Sequences Characterizing k-Trees},
BOOKTITLE = {Computing and Combinatorics, 12th Annual International Conference, COCOON 2006},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4112},
PAGES = {216--225},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Taipei, Taiwan},
ISBN = {3-540-36925-2},
}


Entry last modified by Christine Kiesel, 02/07/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)
Ingmar Weber
Created
06/09/2006 12:16:11 PM
Revisions
2.
1.
0.

Editor(s)
Christine Kiesel
Ingmar Weber
Ingmar Weber

Edit Dates
07.02.2007 17:52:52
09/18/2006 11:17:43 AM
06/09/2006 12:16:11 PM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section