Maximum bipartite subgraph of geometric intersection graphs

DOI10.1007/978-3-030-39881-1_14MaRDI QIDQ782177zbMATH OpenOpenAlexFDO

Authors Satyabrata Jana, Anil Maheshwari, Saeed Mehrabi, Sasanka Roy

Publication date 22 July 2020

Full work available at URL https://arxiv.org/abs/1909.03896

zbMATH Keywords

\texttt{NP}-hardnessapproximation schemesbipartite subgraphgeometric intersection graphstriangle-free subgraph

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Maximum bipartite subgraphs of geometric intersection graphs
• Testing bipartiteness of geometric intersection graphs
• Testing bipartiteness of geometric intersection graphs
• Approximation Algorithms for Geometric Intersection Graphs
• Algorithm Theory - SWAT 2004

Cited in

(6)

• Testing bipartiteness of geometric intersection graphs
• Maximum matchings in geometric intersection graphs
• Graph Bipartization Problem with Applications to Via Minimization in VLSI Design
• Two generalizations of proper coloring: hardness and approximability
• Maximum Bipartite Subgraph of Geometric Intersection Graphs
• Maximum bipartite subgraphs of geometric intersection graphs

This page was built for publication: Maximum bipartite subgraph of geometric intersection graphs

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