\textsc{max-cut} and containment relations in graphs
From MaRDI portal
Publication:441861
DOI10.1016/j.tcs.2012.02.036zbMath1251.90325MaRDI QIDQ441861
Publication date: 8 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.036
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The max-cut problem on graphs not contractible to \(K_ 5\)
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- Graph minors. I. Excluding a forest
- Graph minors. V. Excluding a planar graph
- A polynomial characterization of some graph partitioning problems
- Weakly bipartite graphs and the max-cut problem
- Quickly excluding a forest
- Maximum cut on line and total graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- A characterization of weakly bipartite graphs
- A short proof of Guenin's characterization of weakly bipartite graphs
- Boundary classes of graphs for the dominating set problem
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- NP-hard graph problems and boundary classes of graphs
- max-cut and Containment Relations in Graphs
- A polynomial algorithm for the max-cut problem on graphs without long odd cycles
- Reducibility Among Combinatorial Problems
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Node-and edge-deletion NP-complete problems
- Optimization via enumeration: A new algorithm for the max cut problem
