Structure and linear time recognition of 3-leaf powers

DOI10.1016/j.ipl.2006.01.004zbMath1178.05090OpenAlexW2095559603MaRDI QIDQ844175

Van Bang Le, Andreas Brandstädt

Publication date: 18 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.01.004

zbMATH Keywords

graph algorithmsleaf powerslinear time recognition algorithm3-leaf powers3-leaf rootsleaf roots

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (38)

The scattering number of strictly chordal graphs: linear time determination ⋮ Maximal determinants of combinatorial matrices ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs ⋮ Pairwise Compatibility Graphs: A Survey ⋮ Towards a characterization of leaf powers by clique arrangements ⋮ Polynomial kernels for 3-leaf power graph modification problems ⋮ Grammars and clique-width bounds from split decompositions ⋮ Recognition of linear and star variants of leaf powers is in P ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Recognizing k -Leaf Powers in Polynomial Time, for Constant k ⋮ Pairwise compatibility graphs: complete characterization for wheels ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ The Clique-Width of Tree-Power and Leaf-Power Graphs ⋮ The 3-Steiner Root Problem ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs ⋮ Unnamed Item ⋮ On coloring problems with local constraints ⋮ Boxicity of leaf powers ⋮ Path-bicolorable graphs ⋮ Parameterized Leaf Power Recognition via Embedding into Graph Products ⋮ Rooted directed path graphs are leaf powers ⋮ Characterising \((k,\ell )\)-leaf powers ⋮ Linear time construction of 5-phylogenetic roots for tree chordal graphs ⋮ Exact leaf powers ⋮ Unnamed Item ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ Cycle Extendability of Hamiltonian Strongly Chordal Graphs ⋮ Ptolemaic Graphs and Interval Graphs Are Leaf Powers ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ Path-Bicolorable Graphs ⋮ Simplicial powers of graphs ⋮ The complete inclusion structure of leaf power classes ⋮ A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers ⋮ ON THE PAIRWISE COMPATIBILITY PROPERTY OF SOME SUPERCLASSES OF THRESHOLD GRAPHS ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ Simplicial Powers of Graphs ⋮ On k- Versus (k + 1)-Leaf Powers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizations of strongly chordal graphs
• Distance-hereditary graphs
• Some remarks about leaf roots
• On Graph Powers for Leaf-Labeled Trees
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Algorithms and Computation

This page was built for publication: Structure and linear time recognition of 3-leaf powers