Supermodularity in unweighted graph optimization. I: Branchings and matchings
From MaRDI portal
Publication:5219667
Abstract: The main result of the paper is motivated by the following two, apparently unrelated graph optimization problems: (A) as an extension of Edmonds' disjoint branchings theorem, characterize digraphs comprising disjoint branchings each having a specified number of arcs, (B) as an extension of Ryser's maximum term rank formula, determine the largest possible matching number of simple bipartite graphs complying with degree-constraints. The solutions to these problems and to their generalizations will be obtained from a new min-max theorem on covering a supermodular function by a simple degree-constrained bipartite graph. A specific feature of the result is that its minimum cost extension is already NP-complete. Therefore classic polyhedral tools themselves definitely cannot be sufficient for solving the problem, even though they make some good service in our approach.
Recommendations
Cites work
- A generalization of Kónig's theorem
- A theorem on flows in networks
- An application of submodular flows
- Arborescence problems in directed graphs: theorems and algorithms
- Arc‐disjoint arborescences of digraphs
- Augmentation Problems
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Characterization of digraphic sequences with strongly connected realizations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Combinatorial Properties of Matrices of Zeros and Ones
- Complexity of a disjoint matching problem on bipartite graphs
- Connections in combinatorial optimization
- Covering simply connected regions by rectangles
- Generalized polymatroids and submodular flows
- How to make a digraph strongly connected
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 3906513 (Why is no real title available?)
- scientific article; zbMATH DE number 3580570 (Why is no real title available?)
- scientific article; zbMATH DE number 3799695 (Why is no real title available?)
- scientific article; zbMATH DE number 3325507 (Why is no real title available?)
- Matrices of 0's and 1's with total support
- Minimal edge-coverings of pairs of sets
- On complexity of special maximum matchings constructing
- On Ryser's maximum term rank formula
- On two minimax theorems in graph
- Partitioning to three matchings of given size is NP-complete for bipartite graphs
- Primal-dual approach for directed vertex connectivity augmentation and generalizations
- Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard: A solution to the 2-atom problem in discrete tomography
- Restricted \(t\)-matchings in bipartite graphs
- Studies on directed graphs. I, II
- Supermodularity in unweighted graph optimization. II: Matroidal term rank augmentation
- Supermodularity in unweighted graph optimization. III: Highly connected digraphs
- Term rank of 0,1 matrices
- The Term Rank of a Matrix
Cited in
(15)- An application of submodular flows
- Decreasing minimization on M-convex sets: algorithms and applications
- Fair integral submodular flows
- Packing of maximal independent mixed arborescences
- Packing branchings under cardinality constraints on their root sets
- Optimization over degree sequences of graphs
- Technical Note—Preservation of Supermodularity in Parametric Optimization Problems with Nonlattice Structures
- Supermodularity in unweighted graph optimization. II: Matroidal term rank augmentation
- Supermodularity in unweighted graph optimization. III: Highly connected digraphs
- Packing of spanning mixed arborescences
- Matroid-rooted packing of arborescences
- Approximate cut \& packing ratios for multi-commodity arborescences
- On arborescence packing augmentation in hypergraphs
- Regular packing of rooted hyperforests with root constraints in hypergraphs
- Packing mixed hyperarborescences
This page was built for publication: Supermodularity in unweighted graph optimization. I: Branchings and matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219667)
