Linear-time algorithms for tree root problems
From MaRDI portal
Publication:2346968
DOI10.1007/s00453-013-9815-yzbMath1312.05131OpenAlexW2051982334MaRDI QIDQ2346968
Maw-Shang Chang, Ming-Tat Ko, Hsueh-I Lu
Publication date: 26 May 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9815-y
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Algorithms for the rainbow vertex coloring problem on graph classes, A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph, Parameterized leaf power recognition via embedding into graph products
Cites Work
- Unnamed Item
- On rigid circuit graphs
- A linear time algorithm to list the minimal separators of chordal graphs
- Graph powers and \(k\)-ordered hamiltonicity
- Rooted directed path graphs are leaf powers
- Closest 4-leaf power is fixed-parameter tractable
- Counting clique trees and computing perfect elimination schemes in parallel
- Minimal vertex separators of chordal graphs
- Independence ratios of graph powers
- Computing roots of graphs is hard
- Clique tree generalization and new subclasses of chordal graphs
- A characterisation of rigid circuit graphs
- Algorithmic graph theory and perfect graphs
- Independent sets in graph powers are almost contained in juntas
- Coloring squares of planar graphs with girth six
- Asymptotic values of the Hall-ratio for graph powers
- Strongly simplicial vertices of powers of trees
- A bound on the chromatic number of the square of a planar graph
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Characterization of n-path graphs and of graphs having \(n\)-th root
- On Graph Powers for Leaf-Labeled Trees
- Succinct Representation of Balanced Parentheses and Static Trees
- Bipartite roots of graphs
- The genus of Petersen powers
- Graphs whose powers are chordal and graphs whose powers are interval graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Independent sets in tensor graph powers
- Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon
- Locality in Distributed Graph Algorithms
- Algorithmic Aspects of Vertex Elimination on Graphs
- Tree Powers
- Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
- Graph Classes: A Survey
- The Chromatic Number of Graph Powers
- Coloring Powers of Planar Graphs
- A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
- Recognizing Powers of Proper Interval, Split, and Chordal Graphs
- Computing Phylogenetic Roots with Bounded Degrees and Errors
- Algorithms for Square Roots of Graphs
- Coloring the square of a planar graph
- Average Degree in Graph Powers
- On tree roots of graphs
- Orderly Spanning Trees with Applications
- On Colorings of Squares of Outerplanar Graphs
- A criterion for planarity of the square of a graph
- The square root of a graph
- The square root of a digraph
- Linear-Time Algorithms for Tree Root Problems
