Special edges, and approximating the smallest directed k-edge connected spanning subgraph

MaRDI QIDQ5501264zbMATH OpenFDO

Authors Harold N. Gabow

Publication date 3 August 2015

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Recommendations

• An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph
• scientific article; zbMATH DE number 2079371
• Iterated rounding algorithms for the smallest \(k\)-edge connected spanning subgraph
• A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
• Approximating k-node Connected Subgraphs via Critical Graphs

Cited in

(7)

• An algorithmic metatheorem for directed treewidth
• scientific article; zbMATH DE number 2079371 (Why is no real title available?)
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximating the minimum strongly connected subgraph via a matching lower bound
• A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
• An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph
• On the minimal number of edges in induced subgraphs of special distance graphs

This page was built for publication: Special edges, and approximating the smallest directed \(k\)-edge connected spanning subgraph

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