Maximum cut on line and total graphs
From MaRDI portal
Publication:1304481
DOI10.1016/S0166-218X(99)00056-6zbMath0935.68082MaRDI QIDQ1304481
Publication date: 23 November 1999
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
68P10: Searching and sorting
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C45: Eulerian and Hamiltonian graphs
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- The max-cut problem on graphs not contractible to \(K_ 5\)
- A polynomial characterization of some graph partitioning problems
- Some simplified NP-complete graph problems
- 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