scientific article; zbMATH DE number 3390827

zbMath0247.05151MaRDI QIDQ5659589

G. I. Orlova, Dorfman Jakov

Publication date: 1972

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (39)

Decomposition and optimization over cycles in binary matroids ⋮ Hitting Weighted Even Cycles in Planar Graphs ⋮ Unnamed Item ⋮ On a positive semidefinite relaxation of the cut polytope ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ The max-cut problem on graphs not contractible to \(K_ 5\) ⋮ Unnamed Item ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs ⋮ Partitioning planar graphs: a fast combinatorial approach for max-cut ⋮ Maximum Cut Parameterized by Crossing Number ⋮ A new discrete filled function method for solving large scale max-cut problems ⋮ \textsc{max-cut} and containment relations in graphs ⋮ Finding the maximum cut by the greedy algorithm ⋮ Cuts in undirected graphs. I ⋮ Weakly bipartite graphs and the max-cut problem ⋮ Cardinality constrained minimum cut problems: complexity and algorithms. ⋮ Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ 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 ⋮ An algorithm for min-cost edge-disjoint cycles and its applications ⋮ Canonical dual approach to solving the maximum cut problem ⋮ Triangle-free subcubic graphs with minimum bipartite density ⋮ Ideal clutters ⋮ Optimal cuts in graphs and statistical mechanics ⋮ Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem ⋮ Some simplified NP-complete graph problems ⋮ max-cut and Containment Relations in Graphs ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ The complexity of bottleneck labeled graph problems ⋮ Bipartite subgraphs of triangle-free subcubic graphs ⋮ Path optimization for graph partitioning problems ⋮ Bipartite density of triangle-free subcubic graphs ⋮ Master polytopes for cycles of binary matroids ⋮ Role of redundant constraints for improving dual bounds in polynomial optimization problems ⋮ Hypergraph cuts above the average ⋮ The line index and minimum cut of weighted graphs ⋮ Node and edge relaxations of the max-cut problem

This page was built for publication: