On graph powers for leaf-labeled trees

DOI10.1006/JAGM.2001.1195MaRDI QIDQ2777607zbMATH OpenOpenAlexWikidataFDO

Authors N. 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

zbMATH Keywords

graph power\(k\)-leaf power

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1617253
• Structure and linear-time recognition of 4-leaf powers
• On (k,ℓ)-Leaf Powers
• Structure and linear time recognition of 3-leaf powers
• Characterising \((k,\ell )\)-leaf powers

Cited in

(50)

• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
• On the pairwise compatibility property of some superclasses of threshold graphs
• Leaf realization problem, caterpillar graphs and prefix normal words
• The complete inclusion structure of leaf power classes
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• scientific article; zbMATH DE number 7559376 (Why is no real title available?)
• Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs
• Boxicity of leaf powers
• Exact leaf powers
• Parameterized leaf power recognition via embedding into graph products
• Exact-2-relation graphs
• On k- Versus (k + 1)-Leaf Powers
• Simplicial Powers of Graphs
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• The 3-Steiner Root Problem
• Closest 4-leaf power is fixed-parameter tractable
• Strictly chordal graphs are leaf powers
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• A survey on pairwise compatibility graphs
• On coloring problems with local constraints
• Parameterized leaf power recognition via embedding into graph products
• On pairwise compatibility graphs having Dilworth number \(k\)
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
• Linear-time algorithms for tree root problems
• On the general position number of the k -th power graphs
• Computing optimal leaf roots of chordal cographs in linear time
• Maximal determinants of combinatorial matrices
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Rooted directed path graphs are leaf powers
• New results on pairwise compatibility graphs
• Some remarks about leaf roots
• Polynomial kernels for 3-leaf power graph modification problems
• Simplicial powers of graphs
• Pairwise compatibility graphs: a survey
• Structure and linear time recognition of 3-leaf powers
• Path-bicolorable graphs
• A survey of parameterized algorithms and the complexity of edge modification
• Characterising \((k,\ell )\)-leaf powers
• Structure and linear-time recognition of 4-leaf powers
• Linear time construction of 5-phylogenetic roots for tree chordal graphs
• Recognition of linear and star variants of leaf powers is in P
• Linear-Time Algorithms for Tree Root Problems
• A polynomial kernel for 3-leaf power deletion
• Leaf Powers and Their Properties: Using the Trees
• Characterizing and computing the structure of clique intersections in strongly chordal graphs
• Path-bicolorable graphs. (Extended abstract)
• On graphs that are not PCGs
• scientific article; zbMATH DE number 1617253 (Why is no real title available?)

This page was built for publication: On graph powers for leaf-labeled trees

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