An application of submodular flows
type: Item
instance of: scholarly article
title: An application of submodular flows
zbMATH Open document ID: 0672.05035
DOI: 10.1016/0024-3795(89)90469-2
author: András Frank
author: Éva Tardos
published in: Linear Algebra and its Applications
publication date: 1989-01-01T00:00:00Z
review text: The authors generalize some theorems of Rado and Lovász concerning bipartite graphs and intersecting supermodular functions. As a general model, an optimization problem of finding a supporting set of a matroid having minimum cost is formulated. Several applications of the general results are given for the bipartite graphs and for the optimization problem of finding a minimum-cost subgraph H of a digraph G such that H contains k disjoint paths from a fixed node of G to any other nodes. A characterization for graphs having a branching that meets all directed cuts is obtained. A result of Vidyasankar concerning the optimal covering of a directed graph by arborescences and a theorem of Gröflin and Hoffman on matroid intersection are also extended. Some problems of improving networks are also discussed.
reviewed by: V.Peteanu
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 4099334
zbMATH Keywords: submodular flows
zbMATH Keywords: bipartite graphs
zbMATH Keywords: supermodular functions
zbMATH Keywords: matroid
zbMATH Keywords: minimum-cost subgraph
Wikidata QID: Q56987212
MaRDI profile type: Publication
full work available at URL: 0024-3795(89)90469-2
OpenAlex ID: W2069138465
cites work: Arc‐disjoint arborescences of digraphs
cites work: A Primal-Dual Algorithm for Submodular Flows
cites work: Matroid Intersection
cites work: Q4149476
cites work: Q5514188
cites work: Q3859792
cites work: How to make a digraph strongly connected
cites work: Q4744300
cites work: An Algorithm for Submodular Functions on Graphs
cites work: Finding feasible vectors of Edmonds-Giles polyhedra
cites work: Generalized polymatroids and submodular flows
cites work: Covering directed and odd cuts
cites work: ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
cites work: On matroid intersections
cites work: Q3668292
cites work: Minimum cost flow with set-constraints
cites work: Complexity of Matroid Property Algorithms
cites work: Computing Maximal “Polymatroidal” Network Flows
cites work: A generalization of Kónig's theorem
cites work: Q3934404
cites work: A Minimax Theorem for Directed Graphs
cites work: A THEOREM ON INDEPENDENCE RELATIONS
cites work: Proving total dual integrality with cross-free families—A general framework
cites work: Layered Augmenting Path Algorithms
cites work: Covering the edge set of a directed graph with trees
cites work: Edge-connectivity augmentation problems
cites work: Q4111952
cites work: Minimization on submodular flows
description: scientific article; zbMATH DE number 4099334