The Library
Polynomial-time algorithm for the leafage of chordal graphs
Tools
Habib, Michel and Stacho, Juraj (2009) Polynomial-time algorithm for the leafage of chordal graphs. In: Algorithms - ESA 2009, Copenhagen, Denmark, 7-9 Sep 2009. Published in: Algorithms - ESA 2009, Vol.5757 pp. 290-300. ISBN 9783642041273. doi:10.1007/978-3-642-04128-0_27 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-04128-0_27
Abstract
Every chordal graph G can be represented as the intersection graph of a collection of subtrees of a host tree, the so-called tree model of G. The leafage l(G) of a connected chordal graph G is the minimum number of leaves of the host tree of a tree model of G. This concept was first defined by I.-J. Lin, T.A. McKee, and D.B. West in [9]. In this contribution, we present the first polynomial time algorithm for computing l(G) for a given chordal graph G. In fact, our algorithm runs in time O(n 3) and it also constructs a tree model of G whose host tree has l(G) leaves.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Algorithms - ESA 2009 | ||||
Publisher: | Springer New York LLC | ||||
ISBN: | 9783642041273 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Algorithms - ESA 2009 | ||||
Official Date: | 2009 | ||||
Dates: |
|
||||
Volume: | Vol.5757 | ||||
Page Range: | pp. 290-300 | ||||
DOI: | 10.1007/978-3-642-04128-0_27 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | Algorithms - ESA 2009 | ||||
Type of Event: | Conference | ||||
Location of Event: | Copenhagen, Denmark | ||||
Date(s) of Event: | 7-9 Sep 2009 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |