MPI-INF D1 Publications: Proceedings Article: Sequences Characterizing k-Trees

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

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

Action:

Options:

Goto entry point

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:


(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

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

Attachment Section