Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/802547

OpenURL Link
Title
Leaf powers and their properties: using the trees
Author/Creator
Fellows, Michael R.;  Meister, Daniel;  Rosamond, Frances A.;  Sritharan, R.;  Telle, Jan Arne
Institution
The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
Description
A graph G on n vertices is a k-leaf power (G ∈ Gk) if it is isomorphic to a graph that can be “generated” from a tree T that has n leaves, by taking the leaves to represent vertices of G, and making two vertices adjacent if and only if they are at distance at most k in T. We address two questions in this paper: (1) As k increases, do we always have Gk ⊆ Gk+1 ? Answering an open question of Andreas Brandstädt and Van Bang Le [2,3,1], we show that the answer, perhaps surprisingly, is “no.” (2) How should one design algorithms to determine, for k-leaf powers, if they have some property? One way this can be done is to use the fact that k-leaf powers have bounded cliquewidth. This fact, plus the FPT cliquewidth approximation algorithm of Oum and Seymour [14], combined with the results of Courcelle, Makowsky and Rotics [7], allows us to conclude that properties expressible in a general logic formalism, can be decided in FPT time for k-leaf powers, parameterizing by k. This is wildly inefficient. We explore a different approach, under the assumption that a generating tree is given with the graph. We show that one can use the tree directly to decide the property, by means of a finite-state tree automaton. (A more general theorem has been independently obtained by Blumensath and Courcelle [5].) We place our results in a general context of “tree-definable” graph classes, of which k-leaf powers are one particular example.
Relation
19th International Symposium on Algorithms and Computation (ISAAC 2008). Algorithms and Computation: 19th International Symposium, ISAAC 2008 (Gold Coast, Qld 15-17 December, 2008) p. 402-413
Publisher Link
http://dx.doi.org/10.1007/978-3-540-92182-0_37
Date
2008
Publisher
Springer
Keyword(s)
k-leaf powers;  graphs;  tree;  graph classes
Resource Type
conference paper
Identifier
http://hdl.handle.net/1959.13/802547
Identifier
ISBN:9783540921813
Reviewed
Reviewed
14 Visitors 22 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"Leaf powers and their properties: using the trees"
 
OR