Structure and linear time recognition of 3-leaf powers

DOI10.1016/J.IPL.2006.01.004zbMATH Open1178.05090OpenAlexW2095559603MaRDI QIDQ844175FDOQ844175

Authors: 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

Recommendations

• Structure and linear-time recognition of 4-leaf powers
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• Recognition of linear and star variants of leaf powers is in P
• Linear complexity of ternary sequences formed on the basis of power residue classes
• A polynomial kernel for 3-leaf power deletion
• scientific article; zbMATH DE number 7559376
• On k- Versus (k + 1)-Leaf Powers
• Characterization and Recognition of Partial 3-Trees
• Characterising \((k,\ell )\)-leaf powers
• On the power of border of depth-3 arithmetic circuits

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Graph Classes: A Survey
• Characterizations of strongly chordal graphs
• Distance-hereditary graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Title not available (Why is that?)
• Some remarks about leaf roots
• On graph powers for leaf-labeled trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms and Computation

Cited In (45)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Cycle Extendability of Hamiltonian Strongly Chordal Graphs
• Polynomial kernels for 3-leaf power graph modification problems
• On coloring problems with local constraints
• Some remarks about leaf roots
• Boxicity of leaf powers
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• 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
• On graph powers for leaf-labeled trees
• Exact leaf powers
• Simplicial powers of graphs
• Pairwise compatibility graphs: a survey
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• The 3-Steiner Root Problem
• On (k,ℓ)-Leaf Powers
• Path-bicolorable graphs. (Extended abstract)
• The scattering number of strictly chordal graphs: linear time determination
• Succinct data structures for SP, block-cactus and \(3\)-leaf power graphs
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs
• Computing optimal leaf roots of chordal cographs in linear time
• Characterising \((k,\ell )\)-leaf powers
• Maximal determinants of combinatorial matrices
• Linear time construction of 5-phylogenetic roots for tree chordal graphs
• Polynomial kernels for 3-leaf power graph modification problems
• Closest 4-leaf power is fixed-parameter tractable
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Structure and linear-time recognition of 4-leaf powers
• Parameterized leaf power recognition via embedding into graph products
• Towards a characterization of leaf powers by clique arrangements
• Grammars and clique-width bounds from split decompositions
• The complete inclusion structure of leaf power classes
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• On k- Versus (k + 1)-Leaf Powers
• Simplicial Powers of Graphs
• Parameterized leaf power recognition via embedding into graph products
• On the pairwise compatibility property of some superclasses of threshold graphs
• Rooted directed path graphs are leaf powers
• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
• Path-bicolorable graphs
• Pairwise compatibility graphs: complete characterization for wheels
• Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q844175)