Approximation algorithms for flexible graph connectivity

DOI10.4230/LIPICS.FSTTCS.2021.9MaRDI QIDQ6830507zbMATH OpenFDO

Authors Sylvia Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur

Publication date 5 February 2024

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2021.9

zbMATH Keywords

approximation algorithmscombinatorial optimizationedge-connectivity of graphsnetwork designreliability of networks

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Reliability, availability, maintenance, inspection in operations research (90B25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Cited in

(6)

• On the complexity of finding a sparse connected spanning subgraph in a non-uniform failure model
• Improved approximation algorithms for covering pliable set families and flexible graph connectivity
• When does FTP become FPT??
• When does FTP become FPT?
• Tight analysis of the primal-dual method for edge-covering pliable set families
• Fault-tolerant matroid bases

This page was built for publication: Approximation algorithms for flexible graph connectivity

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