Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\)
From MaRDI portal
Publication:830923
DOI10.1007/s10878-020-00637-6zbMath1467.90049OpenAlexW3048062030MaRDI QIDQ830923
Publication date: 10 May 2021
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-020-00637-6
polynomial algorithmconnected max cutgraphs without the excluded minor \(K_5\backslash e\)Hamilton cycle problemmax cutmin cut
Related Items (2)
Cites Work
- The complexity of minimum convex coloring
- Bemerkungen zu Hadwigers Vermutung
- Some simplified NP-complete graph problems
- Maximum cut on line and total graphs
- Binary Steiner trees: structural results and an exact solution approach
- An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs
- Global optimization of multilevel electricity market models including network design and graph partitioning
- Polytopes associated with symmetry handling
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
- Reducibility among Combinatorial Problems
- Imposing Connectivity Constraints in Forest Planning Models
- Approximation and intractability results for the maximum cut problem and its variants
- Unifying maximum cut and minimum cut of a planar graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\)
