Linear-Time Algorithms for Tree Root Problems

DOI10.1007/11785293_38zbMath1142.05365OpenAlexW1851204491MaRDI QIDQ5757900

Ming-Tat Ko, Hsueh-I Lu, Maw-Shang Chang

Publication date: 7 September 2007

Published in: Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11785293_38

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Recognizing k -Leaf Powers in Polynomial Time, for Constant k ⋮ The Clique-Width of Tree-Power and Leaf-Power Graphs ⋮ The 3-Steiner Root Problem ⋮ Complexity of finding graph roots with girth conditions ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ The square of a block graph ⋮ Finding cut-vertices in the square roots of a graph ⋮ A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ Linear-time algorithms for tree root problems

This page was built for publication: Linear-Time Algorithms for Tree Root Problems