Error compensation in leaf power problems

DOI10.1007/S00453-005-1180-ZMaRDI QIDQ2498407zbMATH OpenOpenAlexFDO

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

Publication date 16 August 2006

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-005-1180-z

zbMATH Keywords

subgraph characterization of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Algorithms and Computation
• Graph-Theoretic Concepts in Computer Science
• Closest 4-leaf power is fixed-parameter tractable
• Polynomial kernels for 3-leaf power graph modification problems
• Polynomial kernels for 3-leaf power graph modification problems

Cited in

(25)

• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
• The complete inclusion structure of leaf power classes
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• scientific article; zbMATH DE number 7559376 (Why is no real title available?)
• Exact leaf powers
• The 3-Steiner Root Problem
• Closest 4-leaf power is fixed-parameter tractable
• On the effectiveness of the incremental approach to minimal chordal edge modification
• Maximal determinants of combinatorial matrices
• Characterizing and computing minimal cograph completions
• Rooted directed path graphs are leaf powers
• Polynomial kernels for 3-leaf power graph modification problems
• On graphs with 2 trivial distance ideals
• Simplicial powers of graphs
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• Graph-Theoretic Concepts in Computer Science
• A survey of parameterized algorithms and the complexity of edge modification
• Algorithms and Computation
• Characterising \((k,\ell )\)-leaf powers
• A more effective linear kernelization for cluster editing
• Characterizing and Computing Minimal Cograph Completions
• A polynomial kernel for 3-leaf power deletion
• Polynomial kernels for 3-leaf power graph modification problems
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion

This page was built for publication: Error compensation in leaf power problems

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