Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings
From MaRDI portal
Publication:5219667
DOI10.1287/moor.2017.0881zbMath1434.05120arXiv1608.05722OpenAlexW2963160020MaRDI QIDQ5219667
Publication date: 12 March 2020
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1608.05722
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items
Fair integral submodular flows, Packing of spanning mixed arborescences, Packing of maximal independent mixed arborescences, Packing branchings under cardinality constraints on their root sets, Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation, Supermodularity in Unweighted Graph Optimization III: Highly Connected Digraphs, Decreasing minimization on M-convex sets: algorithms and applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Studies on directed graphs. I, II
- A theorem on flows in networks
- Term rank of \(0,1\) matrices
- On complexity of special maximum matchings constructing
- Covering simply connected regions by rectangles
- Generalized polymatroids and submodular flows
- An application of submodular flows
- On Ryser's maximum term rank formula
- Matrices of 0's and 1's with total support
- How to make a digraph strongly connected
- On two minimax theorems in graph
- Restricted \(t\)-matchings in bipartite graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Minimal edge-coverings of pairs of sets
- Partitioning to three matchings of given size is NP-complete for bipartite graphs
- Complexity of a disjoint matching problem on bipartite graphs
- Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography
- Characterization of Digraphic Sequences with Strongly Connected Realizations
- Combinatorial Properties of Matrices of Zeros and Ones
- The Term Rank of a Matrix
- Arc‐disjoint arborescences of digraphs
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Augmentation Problems
- Primal-dual approach for directed vertex connectivity augmentation and generalizations
- Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation
- Supermodularity in Unweighted Graph Optimization III: Highly Connected Digraphs
- Arborescence Problems in Directed Graphs: Theorems and Algorithms
- A generalization of Kónig's theorem
