Measuring Indifference: Unit Interval Vertex Deletion

DOI10.1007/978-3-642-16926-7_22zbMath1309.68158OpenAlexW1564033224MaRDI QIDQ3057628

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

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

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) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (14)

Distance from triviality 2.0: hybrid parameterizations ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Proper interval vertex deletion ⋮ Contracting graphs to paths and trees ⋮ A faster FPT algorithm for bipartite contraction ⋮ Unit interval vertex deletion: fewer vertices are relevant ⋮ Unit interval editing is fixed-parameter tractable ⋮ Proper Interval Vertex Deletion ⋮ Vertex deletion problems on chordal graphs ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs ⋮ Modifying a graph using vertex elimination ⋮ Vertex Deletion Problems on Chordal Graphs

Cites Work

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

This page was built for publication: Measuring Indifference: Unit Interval Vertex Deletion