Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\)

DOI10.1007/s10878-020-00637-6zbMath1467.90049OpenAlexW3048062030MaRDI QIDQ830923

Brahim Chaourar

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

zbMATH Keywords

polynomial algorithmconnected max cutgraphs without the excluded minor \(K_5\backslash e\)Hamilton cycle problemmax cutmin cut

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (2)

On the bond polytope ⋮ The spectral radius of minor-free graphs

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\)