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

approximation algorithmscombinatorial optimizationconnectivitygraph and network algorithms

Mathematics Subject Classification ID

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

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)

• A simple certifying algorithm for 3-edge-connectivity
• scientific article; zbMATH DE number 1670548 (Why is no real title available?)
• 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?)
• An approximation algorithm for the minimum co-path set problem
• AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY
• On the maximum size of a minimal \(k\)-edge connected augmentation

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)