Maximum cut on line and total graphs

DOI10.1016/S0166-218X(99)00056-6zbMath0935.68082OpenAlexW2170458234WikidataQ127179048 ScholiaQ127179048MaRDI QIDQ1304481

Venkatesan Guruswami

Publication date: 23 November 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00056-6

zbMATH Keywords

maximum cut problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (15)

Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs ⋮ Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\) ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Complexity of maximum cut on interval graphs ⋮ The maximum cardinality cut problem in co-bipartite chain graphs ⋮ \textsc{max-cut} and containment relations in graphs ⋮ A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ max-cut and Containment Relations in Graphs ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ On the maximum cardinality cut problem in proper interval graphs and related graph classes ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Revising Johnson's table for the 21st century

Cites Work

• 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
• Unnamed Item
• Unnamed Item

This page was built for publication: Maximum cut on line and total graphs