Algorithms – ESA 2005

DOI10.1007/11561071zbMath1162.05357OpenAlexW2501059503MaRDI QIDQ5475831

Zoya Svitkina, Ara Hayrapetyan, Martin Pál, David Kempe

Publication date: 27 June 2006

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11561071

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Parameterized complexity of immunization in the threshold model ⋮ Unbalanced graph partitioning ⋮ Finding the probability of infection in an SIR network is NP-hard ⋮ A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem ⋮ On the minimum \(s-t\) cut problem with budget constraints ⋮ On dissemination thresholds in regular and irregular graph classes ⋮ Approximability of the firefighter problem. Computing cuts over time ⋮ Contrasting the Spread of Misinformation in Online Social Networks ⋮ Approximation algorithms for maximum cut with limited unbalance ⋮ Cut problems in graphs with a budget constraint ⋮ Modularity-maximizing graph communities via mathematical programming ⋮ Approximation algorithms for MAX RES CUT with limited unbalanced constraints ⋮ Structural and algorithmic properties for parametric minimum cuts ⋮ Computational experience with a SDP-based algorithm for maximum cut with limited unbalance ⋮ On efficient vaccine distribution strategy to suppress pandemic using social relation ⋮ Unbalanced graph cuts with minimum capacity ⋮ Unnamed Item ⋮ Multilevel Approaches for the Critical Node Problem ⋮ Unnamed Item ⋮ Approximation algorithms for fragmenting a graph against a stochastically-located threat ⋮ On the inapproximability of minimizing cascading failures under the deterministic threshold model