König Deletion Sets and Vertex Covers above the Matching Size

DOI10.1007/978-3-540-92182-0_73MaRDI QIDQ3597884zbMATH OpenOpenAlexFDO

Authors Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_73

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Tractability of König edge deletion problems
• The complexity of König subgraph problems and above-guarantee vertex cover
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• Paths, flowers and vertex cover
• Quadratic vertex kernel for split vertex deletion

Cited in

(9)

• Tractability of König edge deletion problems
• Faster exact algorithms for some terminal set problems
• On approximability of optimization problems related to red/blue-split graphs
• Structure analysis of some generalizations of matchings and matroids under algorithmic aspects
• Paths, flowers and vertex cover
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• The complexity of König subgraph problems and above-guarantee vertex cover
• On the parameterized vertex cover problem for graphs with perfect matching

This page was built for publication: König Deletion Sets and Vertex Covers above the Matching Size

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