Maximum cut on line and total graphs
From MaRDI portal
Publication:1304481
DOI10.1016/S0166-218X(99)00056-6zbMath0935.68082OpenAlexW2170458234WikidataQ127179048 ScholiaQ127179048MaRDI QIDQ1304481
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
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
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
- 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
