On Graph Powers for Leaf-Labeled Trees
From MaRDI portal
Publication:2777607
DOI10.1006/jagm.2001.1195zbMath0990.68100OpenAlexW2156623776WikidataQ30050190 ScholiaQ30050190MaRDI QIDQ2777607
Naomi Nishimura, Dimitrios M. Thilikos, Prabhakar Ragde
Publication date: 7 March 2002
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/b90208c867c714e16e9b29906b550c29bc9af7a9
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (45)
Structure and linear time recognition of 3-leaf powers ⋮ Maximal determinants of combinatorial matrices ⋮ Pairwise Compatibility Graphs: A Survey ⋮ Towards a characterization of leaf powers by clique arrangements ⋮ Strictly chordal graphs are leaf powers ⋮ New results on pairwise compatibility graphs ⋮ Polynomial kernels for 3-leaf power graph modification problems ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ 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 ⋮ 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 ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Exact-2-relation graphs ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs ⋮ On coloring problems with local constraints ⋮ Boxicity of leaf powers ⋮ Path-bicolorable graphs ⋮ Characterizing and computing the structure of clique intersections in strongly chordal graphs ⋮ Parameterized Leaf Power Recognition via Embedding into Graph Products ⋮ On pairwise compatibility graphs having Dilworth number \(k\) ⋮ 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 ⋮ Some remarks about leaf roots ⋮ Unnamed Item ⋮ Characterizing star-PCGs ⋮ On graphs that are not PCGs ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ Ptolemaic Graphs and Interval Graphs Are Leaf Powers ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ 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 ⋮ A survey on pairwise compatibility graphs ⋮ Linear-time algorithms for tree root problems
This page was built for publication: On Graph Powers for Leaf-Labeled Trees
