Connected max cut is polynomial for graphs without the excluded minor K₅ e

DOI10.1007/S10878-020-00637-6MaRDI QIDQ830923zbMATH OpenOpenAlexFDO

Authors 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

connected max cutgraphs without the excluded minor \(K_5\backslash e\)Hamilton cycle problemmax cutmin cutpolynomial algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• \textsc{max-cut} and containment relations in graphs
• Minimal disconnected cuts in planar graphs
• Max-Cut and containment relations in graphs

Cites work

• An O(Kn (Kn)) algorithm for the Kth best spanning tree in series parallel graphs
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs
• Approximation and intractability results for the maximum cut problem and its variants
• Bemerkungen zu Hadwigers Vermutung
• Binary Steiner trees: structural results and an exact solution approach
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Global optimization of multilevel electricity market models including network design and graph partitioning
• scientific article; zbMATH DE number 16725 (Why is no real title available?)
• scientific article; zbMATH DE number 59236 (Why is no real title available?)
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• Imposing Connectivity Constraints in Forest Planning Models
• Maximum cut on line and total graphs
• Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
• Polytopes associated with symmetry handling
• Reducibility among combinatorial problems
• Some simplified NP-complete graph problems
• The complexity of minimum convex coloring
• Unifying maximum cut and minimum cut of a planar graph

Cited in

(4)

• Max-Cut and containment relations in graphs
• On the bond polytope
• The spectral radius of minor-free graphs
• Connected max cut is polynomial for graphs without K₅\backslash e as a minor

This page was built for publication: Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q830923)