Error compensation in leaf power problems

DOI10.1007/s00453-005-1180-zzbMath1095.68080OpenAlexW2147251480MaRDI QIDQ2498407

Michael Dom, Falk Hüffner, Jiong Guo, 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

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (23)

On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Maximal determinants of combinatorial matrices ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Towards a characterization of leaf powers by clique arrangements ⋮ On graphs with 2 trivial distance ideals ⋮ Polynomial kernels for 3-leaf power graph modification problems ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ The 3-Steiner Root Problem ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Rooted directed path graphs are leaf powers ⋮ Characterising \((k,\ell )\)-leaf powers ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Characterizing and computing minimal cograph completions ⋮ Unnamed Item ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ Ptolemaic Graphs and Interval Graphs Are Leaf Powers ⋮ A more effective linear kernelization for cluster editing ⋮ Simplicial powers of graphs ⋮ The complete inclusion structure of leaf power classes ⋮ A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers ⋮ An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

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