×

zbMATH — the first resource for mathematics

Max-cut in circulant graphs. (English) Zbl 0769.05059
Summary: We study the max-cut problem in circulant graphs \(C_{n,r}\), where \(C_{n,r}\) is a graph whose edge set consists of a cycle of length \(n\) and all the vertex pairs of distance \(r\) on the cycle. An efficient solution of the problem is obtained so that we show that there is always a maximum cut of a particular shape, called a \(t\)-regular cut. The number of edges of a \(t\)-regular cut can easily be computed. This gives an \(O(r\log^ 2n)\) time algorithm for the max-cut.
We present also some new classes of facets of the bipartite subgraph polytope and the cut polytope, which are spanned by \(t\)-regular cuts.

MSC:
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alspach, B.; Parsons, T.D., Isomorphism of circulant graphs and digraphs, Discrete math., 25, 97-108, (1979) · Zbl 0402.05038
[2] Barahona, F.; Grötschel, M.; Manjoub, A.R., Facets of the bipartite subgraph polytope, Math. oper. res., 10, 340-358, (1985) · Zbl 0578.05056
[3] Barahona, F.; Mahjoub, A.R., On the cut polytope, Math. programming, 36, 157-173, (1986) · Zbl 0616.90058
[4] M. Deza and M. Laurent, Facets of the complete cut cone I, Math. Programming, to appear. · Zbl 0768.90074
[5] Boesch, F.; Tindell, R., Circulants and their connectivities, J. graph theory, 8, 487-499, (1984) · Zbl 0549.05048
[6] Garey, M.R.; Johnson, D.S.; Stockmayer, L., Some simplified NP-complete problems, Theoret. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120
[7] Hopkins, G.; Staton, W., Extremal bipartite subgraphs of cubic triangle free graphs, J. graph theory, 6, 115-121, (1982) · Zbl 0486.05036
[8] Locke, S.C., Maximum k-colorable subgraphs, J. graph theory, 6, 123-132, (1982) · Zbl 0475.05034
[9] Nešetřil, J.; Poljak, S., A note on MAX-cut problem with an application to discrete/analogue convertors, Oper. res. lett., 4, 289-291, (1986) · Zbl 0585.90085
[10] Poljak, S.; Turzík, D., A polynomial time algorithm for constructing a large bipartite subgraph, with an application to a satisfiability problem, Canad. J. math., 34, 519-524, (1982) · Zbl 0471.68041
[11] Poljak, S.; Turzík, D., A polynomial heuristic for certain subgraph optimization problems with guaranteed lower bound, Discrete math., 58, 99-104, (1986) · Zbl 0585.05032
[12] Polyjak, S.; Turzík, D., On a facet of the balanced subgraph polytope, Časopis Pěst. mat., 112, 373-380, (1987) · Zbl 0643.05059
[13] Poljak, S.; Tuza, Z., Maximum bipartite subgraphs of Kneser graphs, Graphs combin., 3, 191-199, (1987) · Zbl 0674.05064
[14] Wang, J.F., The number of spanning trees in circulant graphs, Internat. J. comput. math., 16, 229-241, (1984) · Zbl 0554.05019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.