Linear-Time Algorithms for Tree Root Problems

DOI10.1007/11785293_38MaRDI QIDQ5757900zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Linear-time algorithms for tree root problems
• On tree roots of graphs
• The 3-Steiner Root Problem
• Tree Powers
• On graph powers for leaf-labeled trees

Cited in

(20)

• Minimax Trees in Linear Time with Applications
• A linear time algorithm for the feasibility of pebble motion on trees
• Linear-time algorithms for tree root problems
• Linear-time construction of treaps and Cartesian trees
• scientific article; zbMATH DE number 1496857 (Why is no real title available?)
• The square of a block graph
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• A linear-time algorithm for the feasibility of pebble motion on trees
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• The 3-Steiner Root Problem
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• A Linear Time Algorithm for Finding ak-Tree Core
• Closest 4-leaf power is fixed-parameter tractable
• scientific article; zbMATH DE number 2080269 (Why is no real title available?)
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Complexity of finding graph roots with girth conditions
• Navigating Forest Straight-Line Programs in Constant Time
• On tree roots of graphs
• Finding cut-vertices in the square roots of a graph
• The tree inclusion problem

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

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