max-cut and Containment Relations in Graphs
From MaRDI portal
Publication:3057609
DOI10.1007/978-3-642-16926-7_4zbMath1309.05173OpenAlexW1530503246MaRDI QIDQ3057609
Publication date: 16 November 2010
Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_4
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (1)
Cites Work
- 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
- A polynomial algorithm for the max-cut problem on graphs without long odd cycles
- 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
This page was built for publication: max-cut and Containment Relations in Graphs
