\textsc{max-cut} and containment relations in graphs

DOI10.1016/j.tcs.2012.02.036zbMath1251.90325MaRDI QIDQ441861

Marcin Kaminski

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

zbMATH Keywords

minor; induced subgraph; subgraph; \textsc{max-cut}

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

Related Items

NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Complexity of maximum cut on interval graphs, Seminormality, canonical modules, and regularity of cut polytopes, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, Boundary classes for graph problems involving non-local properties

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item