Measuring indifference: unit interval vertex deletion

DOI10.1007/978-3-642-16926-7_22MaRDI QIDQ3057628zbMATH OpenOpenAlexFDO

Authors René van Bevern, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier

Publication date 16 November 2010

Published in Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16926-7_22

Mathematics Subject Classification ID

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

Recommendations

• Unit interval vertex deletion: fewer vertices are relevant
• Vertex deletion problems on chordal graphs
• Interval deletion is fixed-parameter tractable

Cites work

• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
• A linear time recognition algorithm for proper interval graphs
• A strengthening of Ben Rebea's lemma
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Chordal deletion is fixed-parameter tractable
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Finding odd cycle transversals.
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Kernelization: new upper and lower bound techniques
• Proper Interval Vertex Deletion
• Semiorders and a Theory of Utility Discrimination
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• Some simplified NP-complete graph problems
• The node-deletion problem for hereditary properties is NP-complete
• Utility Maximization, Choice and Preference

Cited in

(12)

• Unit interval vertex deletion: fewer vertices are relevant
• Vertex deletion problems on chordal graphs
• Proper interval vertex deletion
• Declawing a graph: polyhedra and branch-and-cut algorithms
• Distance from triviality 2.0: hybrid parameterizations
• Modifying a graph using vertex elimination
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• Proper Interval Vertex Deletion
• Vertex deletion problems on chordal graphs
• The parameterized complexity of cycle packing: indifference is not an issue
• On the complexity of vertex-splitting into an interval graph

This page was built for publication: Measuring indifference: unit interval vertex deletion

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