Error compensation in leaf power problems
From MaRDI portal
Publication:2498407
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
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
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
