Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems

DOI10.1016/S0166-218X(02)00570-XzbMath1030.90094MaRDI QIDQ1406022

András A. Benczúr

Publication date: 9 September 2003

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

zbMATH Keywords

optimization problems; edge augmentation

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

Related Items

Jump Number of Two-Directional Orthogonal Ray Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A minimax theorem on intervals
• Edge-connectivity augmentation problems
• The ellipsoid method and its consequences in combinatorial optimization
• A weighted min-max relation for intervals
• Parallel and fast sequential algorithms for undirected edge connectivity augmentation
• Finding minimum generators of path systems
• On the optimal vertex-connectivity augmentation
• Minimal edge-coverings of pairs of sets
• Efficient splitting off algorithms for graphs
• An algorithm for covering polygons with rectangles
• The minimum augmentation of any graph to aK-edge-connected graph
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Augmenting Undirected Edge Connectivity in Õ(n2) Time
• Irredundant intervals
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs