On approximability of optimization problems related to red/blue-split graphs
From MaRDI portal
Publication:2399618
DOI10.1016/j.tcs.2017.06.008zbMath1372.68141MaRDI QIDQ2399618
Saket Saurabh, Sounaka Mishra, Shijin Rajakrishnan
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
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms