An Algorithm for Submodular Functions on Graphs

DOI10.1016/S0304-0208(08)72446-0zbMath0504.05059OpenAlexW1483973251MaRDI QIDQ4739952

András Frank

Publication date: 1982

Published in: North-Holland Mathematics Studies (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-0208(08)72446-0

zbMATH Keywords

maximum weight common independent set of two matroidsminimum cost strongly connected orientationminimum weight covering of directed cuts of a digraph

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Graph theory (05C99) Directed graphs (digraphs), tournaments (05C20) Algorithms in computer science (68W99)

Related Items (49)

Eulerian Orientations and Circulations ⋮ Increasing digraph arc-connectivity by arc addition, reversal and complement ⋮ Linear and combinatorial sharing problems ⋮ Convexity and Steinitz's exchange property ⋮ A Mazur-Orlicz type theorem for submodular set functions ⋮ Quadratic M-convex and L-convex functions ⋮ An algorithm for minimum cost arc-connectivity orientations ⋮ On unique extensions of positive additive set functions. II ⋮ Optimum partitioning into intersections of ring families ⋮ Principal structure of submodular systems and Hitchcock-type independent flows ⋮ Sandwich theorems for set functions ⋮ Fair integral submodular flows ⋮ Generalized polymatroids and submodular flows ⋮ Directed submodularity, ditroids and directed submodular flows ⋮ An application of submodular flows ⋮ On orientations and shortest paths ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams ⋮ Improved bound for the Carathéodory rank of the bases of a matroid ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ Monge properties, discrete convexity and applications ⋮ A Survey on Covering Supermodular Functions ⋮ Recent Developments in Discrete Convex Analysis ⋮ Enumerating \(k\)-arc-connected orientations ⋮ How to make a digraph strongly connected ⋮ Minimization on submodular flows ⋮ Degree bounded matroids and submodular flows ⋮ Tree-compositions and orientations ⋮ A dual algorithm for submodular flow problems ⋮ A cost-scaling algorithm for \(0-1\) submodular flows ⋮ Proving total dual integrality with cross-free families—A general framework ⋮ Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs ⋮ Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions ⋮ Critical duality ⋮ \(M\)-convex functions and tree metrics ⋮ Structures of polyhedra determined by submodular functions on crossing families ⋮ Agreeable bets with multiple priors ⋮ A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows ⋮ Duality for balanced submodular flows ⋮ Polymatroidal flows with lower bounds ⋮ Submodular function minimization ⋮ Inverse problems of submodular functions on digraphs ⋮ Fenchel-type duality for matroid valuations ⋮ Discrete convex analysis ⋮ Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs ⋮ Extension of M-convexity and L-convexity to polyhedral convex functions ⋮ Recent trends in combinatorial optimization ⋮ Improved Randomized Algorithm for k-Submodular Function Maximization ⋮ Finding feasible vectors of Edmonds-Giles polyhedra

This page was built for publication: An Algorithm for Submodular Functions on Graphs