On approximability of optimization problems related to red/blue-split graphs
From MaRDI portal
Publication:2399618
DOI10.1016/j.tcs.2017.06.008zbMath1372.68141OpenAlexW2698797805MaRDI QIDQ2399618
Saket Saurabh, Shijin Rajakrishnan, Sounaka Mishra
Publication date: 24 August 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.06.008
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- A characterization of the graphs in which the transversal number equals the matching number
- The complexity of König subgraph problems and above-guarantee vertex cover
- On the hardness of approximating minimum vertex cover
- Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
- Ear-decompositions of matching-covered graphs
- Matching theory
- Optimization, approximation, and complexity classes
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- König-Egerváry graphs, 2-bicritical graphs and fractional matchings
- An efficiently solvable graph partition problem to which many problems are reducible
- Parametrized complexity theory.
- Approximation Algorithms for Steiner and Directed Multicuts
- Covering Graphs by Colored Stable Sets
- Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
- König Deletion Sets and Vertex Covers above the Matching Size
- Faster Parameterized Algorithms Using Linear Programming
- Reducibility among Combinatorial Problems
- Paths, Trees, and Flowers
- Parameterized Algorithms
