On approximability of optimization problems related to red/blue-split graphs

DOI10.1016/J.TCS.2017.06.008MaRDI QIDQ2399618zbMATH OpenOpenAlexFDO

Authors Sounaka Mishra, Shijin Rajakrishnan, Saket Saurabh

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

zbMATH Keywords

approximation algorithmsparametrized complexityred/blue-split graphsKönig-Egerváry graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Approximation schemes for degree-restricted MST and red-blue separation problems
• scientific article; zbMATH DE number 2038709
• The \textsc{red-blue separation} problem on graphs
• The \textsc{Red-Blue Separation} problem on graphs
• Linear algorithms for red and blue domination in convex bipartite graphs
• scientific article; zbMATH DE number 7650095
• On the approximation of Min Split-coloring and Min Cocoloring
• Approximation Algorithms for Some Graph Partitioning Problems
• scientific article; zbMATH DE number 1617261
• Approximation algorithms for maximization problems arising in graph partitioning

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A characterization of the graphs in which the transversal number equals the matching number
• An efficiently solvable graph partition problem to which many problems are reducible
• Approximation Algorithms for Steiner and Directed Multicuts
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Covering Graphs by Colored Stable Sets
• Ear-decompositions of matching-covered graphs
• Faster parameterized algorithms using linear programming
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• König Deletion Sets and Vertex Covers above the Matching Size
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• Matching theory
• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• Parameterized algorithms
• Parametrized complexity theory.
• Paths, Trees, and Flowers
• Reducibility among combinatorial problems
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• The complexity of König subgraph problems and above-guarantee vertex cover
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems

Cited in

(4)

• Some optimization problems on weak-bisplit graphs
• Note on maximal split-stable subgraphs
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
• Covering Graphs by Colored Stable Sets

This page was built for publication: On approximability of optimization problems related to red/blue-split graphs

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