A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity

DOI10.1007/978-3-540-73951-7_5MaRDI QIDQ3603513zbMATH OpenOpenAlexFDO

Authors Prabhakar Gubbala, Balaji Raghavachari

Publication date 17 February 2009

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

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_5

zbMATH Keywords

combinatorial optimizationapproximation algorithmsconnectivitygraph and network algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Connectivity (05C40)

Recommendations

• scientific article; zbMATH DE number 2079404
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem
• scientific article; zbMATH DE number 2119647
• A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem

Cited in

(8)

• scientific article; zbMATH DE number 1670548 (Why is no real title available?)
• On the maximum size of a minimal \(k\)-edge connected augmentation
• A simple certifying algorithm for 3-edge-connectivity
• An approximation algorithm for the minimum co-path set problem
• AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem
• scientific article; zbMATH DE number 2079404 (Why is no real title available?)
• scientific article; zbMATH DE number 2119647 (Why is no real title available?)

This page was built for publication: A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity

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