Max-cut in circulant graphs

DOI10.1016/0012-365X(92)90690-HzbMath0769.05059OpenAlexW1981069811MaRDI QIDQ1201272

Svatopluk Poljak, Daniel Turzík

Publication date: 17 January 1993

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

Full work available at URL: https://doi.org/10.1016/0012-365x(92)90690-h

zbMATH Keywords

cyclecut polytopecirculant graphsmax-cut problembipartite subgraph polytope\(t\)-regular cut

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Related Items (6)

The Boolean Quadric Polytope ⋮ Application of cut polyhedra. I ⋮ Generalised 2-circulant inequalities for the max-cut problem ⋮ A note on the 2-circulant inequalities for the MAX-cut problem ⋮ On the bond polytope ⋮ A new separation algorithm for the Boolean quadric and cut polytopes

Cites Work

• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• A remark on max-cut problem with an application to digital-analogue convertors
• Maximum bipartite subgraphs of Kneser graphs
• Facets for the cut cone. I
• Some simplified NP-complete graph problems
• Isomorphism of circulant graphs and digraphs
• On the number of spanning trees of circulant graphs
• Circulants and their connectivities
• Facets of the Bipartite Subgraph Polytope
• On a facet of the balanced subgraph polytope
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• Maximumk-colorable subgraphs
• Extremal bipartite subgraphs of cubic triangle-free graphs
• On the cut polytope

This page was built for publication: Max-cut in circulant graphs