Weakly bipartite graphs and the max-cut problem
From MaRDI portal
Publication:1169411
DOI10.1016/0167-6377(81)90020-1zbMath0494.90078OpenAlexW2082001376MaRDI QIDQ1169411
Martin Grötschel, William R. Pulleyblank
Publication date: 1981
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(81)90020-1
shortest pathplanar graphspolynomial time algorithmellipsoid methodmax- cut problemweakly bipartite graphs
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)
Related Items
Solving matching problems with linear programming, Multiple phase tabu search for bipartite Boolean quadratic programming with partitioned variables, Complexity and Polynomially Solvable Special Cases of QUBO, Applications of cut polyhedra. II, Unnamed Item, Binary group and Chinese postman polyhedra, Fast Distributed Approximation for Max-Cut, Facets of the \(k\)-partition polytope, A nonmonotone GRASP, New algorithms for the weighted maximum cut problem on graphs, The max-cut problem on graphs not contractible to \(K_ 5\), Even-cycle decompositions of graphs with no odd-\(K_4\)-minor, Graphic vertices of the metric polytope, Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization, Small bipartite subgraph polytopes, Separator-based data reduction for signed graph balancing, The minimum chromatic violation problem: a polyhedral approach, Separation problems for the stable set polytope, A modeling and computational study of the frustration index in signed networks, Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center, LP extreme points and cuts for the fixed-charge network design problem, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Polyhedral results for the bipartite induced subgraph problem, Maximum Cut Parameterized by Crossing Number, \textsc{max-cut} and containment relations in graphs, Separating multi-oddity constrained shortest circuits over the polytope of stable multisets., Unnamed Item, A New Composite Algorithm for Clustering Problems, Cuts in undirected graphs. I, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, A note on line digraphs and the directed max-cut problem, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Finding a shortest cycle in a subspace of the cycle space of a graph, On a composition of independence systems by circuit identification, Faster separation of 1-wheel inequalities by graph products, A polyhedral approach to the feedback vertex set problem, A polynomial algorithm for the max-cut problem on graphs without long odd cycles, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Compositions in the bipartite subgraph polytope, Facets for the cut cone. I, Finding a shortest non-zero path in group-labeled graphs via permanent computation, A tutorial on branch and cut algorithms for the maximum stable set problem, Optimal cuts in graphs and statistical mechanics, Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem, max-cut and Containment Relations in Graphs, Finding shorter cycles in a weighted graph, From Graph Orientation to the Unweighted Maximum Cut, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, On Four Problems in Graph Theory, On fractional cut covers, Unnamed Item, Role of redundant constraints for improving dual bounds in polynomial optimization problems, A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams, The complexity of determining a shortest cycle of even length, The line index and minimum cut of weighted graphs, A characterization of weakly bipartite graphs, A short proof of Guenin's characterization of weakly bipartite graphs, On some weakly bipartite graphs, Fractional covering by cuts, Laplacian eigenvalues and the maximum cut problem, \(K_ i\)-covers. I: Complexity and polytopes, 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, An efficient Dijkstra-like labeling method for computing shortest odd/even paths, A fast algorithm for minimum weight odd circuits and cuts in planar graphs
Cites Work
