Minimizing a monotone concave function with laminar covering constraints

DOI10.1016/j.dam.2007.04.016zbMath1182.90075OpenAlexW2095256337MaRDI QIDQ943837

Mariko Sakashita, Satoru Fujishige, Kazuhisa Makino

Publication date: 10 September 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.04.016

zbMATH Keywords

edge-connectivity augmentationsource locationlaminar cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30) Combinatorial optimization (90C27)

Related Items

Approximating minimum cost source location problems with local vertex-connectivity demands ⋮ Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on minimizing submodular functions
• Edge-connectivity augmentation problems
• Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
• Submodular functions and optimization.
• Locating Sources to Meet Flow Demands in Undirected Networks
• The minimum augmentation of any graph to aK-edge-connected graph
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• A Reduction Method for Edge-Connectivity in Graphs
• Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• Augmenting Undirected Edge Connectivity in Õ(n2) Time
• Edge connectivity between nodes and node-subsets
• Algorithms and Computation