Linear-Time Algorithms for Tree Root Problems

DOI10.1007/11785293_38zbMATH Open1142.05365OpenAlexW1851204491MaRDI QIDQ5757900FDOQ5757900

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

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

Mathematics Subject Classification ID

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

Cited In (21)

• 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
• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• Linear-time construction of treaps and Cartesian trees
• Title not available (Why is that?)
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• The square of a block graph
• 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 ak-Tree Core
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• Title not available (Why is that?)
• Closest 4-leaf power is fixed-parameter tractable
• Complexity of finding graph roots with girth conditions
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• 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)