scientific article

Publication date: 1983

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

survey bipartite graphs matroids matchings network flows perfect graphs multicommodity flows arborescences max-flow min-cut theorem total dual integrality total unimodularity directed cuts blockers submodular functions clutters blocking and anti-blocking polyhedra Min-max relations in combinatorial optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Integer programming (90C10) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (88)

Strengthening topological colorful results for graphs ⋮ On the cycle polytope of a binary matroid ⋮ Polyhedral proof methods in combinatorial optimization ⋮ On the independent dominating set polytope ⋮ Fast approximation for computing the fractional arboricity and extraction of communities of a graph ⋮ Free multiflows in bidirected and skew-symmetric graphs ⋮ Note on maximal split-stable subgraphs ⋮ The complexity of vector partition ⋮ Directed submodularity, ditroids and directed submodular flows ⋮ On \(0,\pm 1\) matrices, odd vectors, and bisubmodular polyhedra ⋮ Maximum flow under proportional delay constraint ⋮ A multivariate framework for weighted FPT algorithms ⋮ Minmax relations for cyclically ordered digraphs ⋮ On box-perfect graphs ⋮ Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound ⋮ Cohen-Macaulayness of monomial ideals and symbolic powers of Stanley-Reisner ideals ⋮ Multi-objective matroid optimization with ordinal weights ⋮ The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect ⋮ Compression with wildcards: all exact or all minimal hitting sets ⋮ A transitivity analysis of bipartite rankings in pairwise multi-class classification ⋮ The parity Hamiltonian cycle problem ⋮ A perfect secret sharing scheme for general access structures ⋮ The stable set polytope of icosahedral graphs ⋮ T-joins in strongly connected hypergraphs ⋮ Shifted matroid optimization ⋮ A short proof of the tree-packing theorem ⋮ Packing cycles in graphs ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ A characterization of the 2-additive Choquet integral through cardinal information ⋮ The complexity of recursive constraint satisfaction problems ⋮ Replication in critical graphs and the persistence of monomial ideals ⋮ A comparison of lower bounds for the symmetric circulant traveling salesman problem ⋮ 2-clique-bond of stable set polyhedra ⋮ Derandomization of auctions ⋮ Cohen-Macaulayness of large powers of Stanley-Reisner ideals ⋮ The edge covering number of the intersection of two matroids ⋮ Polyhedral results for a vehicle routing problem ⋮ Fast approximation of matroid packing and covering ⋮ Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems ⋮ A relax-and-cut algorithm for the set partitioning problem ⋮ A weighted min-max relation for intervals ⋮ Shellable graphs and sequentially Cohen-Macaulay bipartite graphs ⋮ The joy of implications, aka pure Horn formulas: mainly a survey ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ Ordered weighted average optimization in multiobjective spanning tree problem ⋮ Brick partitions of graphs ⋮ A reduction approach to the repeated assignment problem ⋮ Equality of ordinary and symbolic powers of Stanley-Reisner ideals ⋮ A model predictive control approach for discrete-time rescheduling in complex central railway station areas ⋮ The generic rank of body-bar-and-hinge frameworks ⋮ An LP-based heuristic algorithm for the node capacitated in-tree packing problem ⋮ In search of the densest subgraph ⋮ Integral polyhedra related to integer multicommodity flows on a cycle ⋮ Complexity and approximation of the constrained forest problem ⋮ A competitive partnership formation process ⋮ Spectral methods for graph clustering - a survey ⋮ Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree ⋮ Multicommodity flows in cycle graphs ⋮ Some formulations for the group Steiner tree problem ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ Uniform and monotone line sum optimization ⋮ On a cardinality-constrained transportation problem with market choice ⋮ Shared processor scheduling of multiprocessor jobs ⋮ Perfect graphs with polynomially computable kernels ⋮ The uniqueness property for networks with several origin-destination pairs ⋮ A one-to-one correspondence between colorings and stable sets ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are \(\mathcal{G}\)-perfect ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ A new contraction technique with applications to congruency-constrained cuts ⋮ Cache me if you can: capacitated selfish replication games in networks ⋮ Upper and lower degree-constrained graph orientation with minimum penalty ⋮ Paintshop, odd cycles and necklace splitting ⋮ Maximum balanced flow in a network ⋮ Rees algebras of filtrations of covering polyhedra and integral closure of powers of monomial ideals ⋮ Integrality properties of edge path tree families ⋮ Perfectness and imperfectness of unit disk graphs on triangular lattice points ⋮ The \(d\)-dimensional rigidity matroid of sparse graphs ⋮ Coloring by two-way independent sets ⋮ On partitioning two matroids into common independent subsets ⋮ On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs ⋮ Orientations and detachments of graphs with prescribed degrees and connectivity ⋮ A note on matchings and separability ⋮ A duality theorem for the ic-resurgence of edge ideals ⋮ Edge-disjoint paths in planar graphs ⋮ An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality ⋮ The generalized assignment problem with minimum quantities

This page was built for publication: