Closest 4-leaf power is fixed-parameter tractable

DOI10.1016/j.dam.2008.01.007zbMath1156.05057OpenAlexW2128112899MaRDI QIDQ1003724

Rolf Niedermeier, Jiong Guo, Falk Hüffner, Michael Dom

Publication date: 4 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.01.007

zbMATH Keywords

graph algorithmfixed-parameter tractabilitygraph powergraph modificationforbidden subgraph characterizationleaf power

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Polynomial kernels for 3-leaf power graph modification problems ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Boxicity of leaf powers ⋮ Linear-time algorithms for tree root problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correlation clustering
• Graph-modeled data clustering: Exact algorithms for clique generation
• Structure and linear time recognition of 3-leaf powers
• Computing phylogenetic roots with bounded degrees and errors is NP-complete
• Strictly chordal graphs are leaf powers
• NP-hard problems in hierarchical-tree clustering
• Computing roots of graphs is hard
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Cluster graph modification problems
• Parametrized complexity theory.
• Some remarks about leaf roots
• Error compensation in leaf power problems
• Clustering with qualitative information
• On Graph Powers for Leaf-Labeled Trees
• Bipartite roots of graphs
• The 3-Steiner Root Problem
• A More Effective Linear Kernelization for Cluster Editing
• Tree Powers
• Graph Classes: A Survey
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Algorithms for Square Roots of Graphs
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Efficient Parameterized Preprocessing for Cluster Editing
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Computing bounded-degree phylogenetic roots of disconnected graphs
• Computing and Combinatorics
• Linear-Time Algorithms for Tree Root Problems
• Algorithms and Computation
• Aggregating inconsistent information

This page was built for publication: Closest 4-leaf power is fixed-parameter tractable