Making Bipartite Graphs DM-Irreducible

DOI10.1137/16M1106717zbMath1381.05052arXiv1612.08828OpenAlexW2963249783MaRDI QIDQ4604647

Kristóf Bérczi, Satoru Iwata, Jun Kato, Yutaro Yamaguchi

Publication date: 5 March 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.08828

zbMATH Keywords

bipartite graphsmatroid intersectionconnectivity augmentationDM-decomposition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (3)

How to Secure Matchings against Edge Failures ⋮ Making bidirected graphs strongly connected ⋮ How to Secure Matchings Against Edge Failures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm to increase the node-connectivity of a digraph by one
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• Bargaining in a network of buyers and sellers.
• Efficient theoretic and practical algorithms for linear matroid intersection problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Minimal edge-coverings of pairs of sets
• Submodular functions and optimization.
• Maximal Flow Through a Network
• Coverings of Bipartite Graphs
• Augmentation Problems
• Exact and Approximation Algorithms for Weighted Matroid Intersection
• Primal-dual approach for directed vertex connectivity augmentation and generalizations
• Depth-First Search and Linear Graph Algorithms
• Matrices and matroids for systems analysis

This page was built for publication: Making Bipartite Graphs DM-Irreducible