scientific article; zbMATH DE number 437534

MaRDI QIDQ3140408zbMATH OpenFDO

Authors Naveen Garg, Vempala S. Santosh, Aman Singla

Publication date 2 January 1994

zbMATH Keywords

biconnected subgraphsNP-hard

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 871896
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• scientific article; zbMATH DE number 2079404
• scientific article; zbMATH DE number 1688381
• Biconnectivity approximations and graph carvings

Cited in

(14)

• On finding a biconnected spanning planar subgraph with applications to the facilities layout problem
• Finding 2-edge connected spanning subgraphs.
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
• Approximating unweighted connectivity problems in parallel
• Approximating minimum size \{1,2\}-connected networks
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• Pruning 2-connected graphs
• scientific article; zbMATH DE number 871896 (Why is no real title available?)
• Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
• Approximation and Online Algorithms
• A polyhedral approach to planar augmentation and related problems
• Towards more precise parallel biconnectivity approximation
• A 4/3 approximation for 2-vertex-connectivity
• A PTAS for weighted triangle-free 2-matching

This page was built for publication:

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