Cut Problems in Graphs with a Budget Constraint

DOI10.1007/11682462_41MaRDI QIDQ3525779zbMATH OpenOpenAlexFDO

Authors Roee Engelberg, Jochen Könemann, Joseph (Seffi) Naor, Stefano Leonardi

Publication date 18 September 2008

Published in LATIN 2006: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.1984

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Cut problems in graphs with a budget constraint
• Multi-budgeted directed cuts
• Multi-budgeted directed cuts
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithm Theory - SWAT 2004

Cited in

(14)

• Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions
• On the linear relaxation of the \(s-t\)-cut problem with budget constraints
• Approximation algorithms for fragmenting a graph against a stochastically-located threat
• Cut problems in graphs with a budget constraint
• Bounded size graph clustering with applications to stream processing
• A derandomized approximation algorithm for the critical node detection problem
• A randomized algorithm with local search for containment of pandemic disease spread
• Approximation algorithms for multi-budgeted network design problems
• Multi-budgeted directed cuts
• Compact oblivious routing
• Approximability of the k‐server disconnection problem
• On the minimum \(s-t\) cut problem with budget constraints
• Multi-budgeted directed cuts
• Multistage graph problems on a global budget

This page was built for publication: Cut Problems in Graphs with a Budget Constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3525779)