Strongly connected spanning subgraph for almost symmetric networks

DOI10.1142/S0218195917500042MaRDI QIDQ3132920zbMATH OpenOpenAlexFDO

Authors A. Karim Abu-Affash, Paz Carmi, Anat Parush Tzur

Publication date 31 January 2018

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195917500042

zbMATH Keywords

computational geometryapproximation algorithms\(t\)-spannersstrongly connected subgraphssymmetric disk graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Approximating the minimum strongly connected subgraph via a matching lower bound
• Min-power strong connectivity
• Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs
• Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
• Finding sparser directed spanners

Cites work

• scientific article; zbMATH DE number 1670548 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305417 (Why is no real title available?)
• scientific article; zbMATH DE number 2079404 (Why is no real title available?)
• scientific article; zbMATH DE number 2119646 (Why is no real title available?)
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Approximating the Minimum Equivalent Digraph
• Approximating the minimum strongly connected subgraph via a matching lower bound
• Approximation Algorithms for Several Graph Augmentation Problems
• Augmentation Problems
• Biconnectivity approximations and graph carvings
• Introduction to algorithms
• On strongly connected digraphs with bounded cycle length
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• P-Complete Approximation Problems

Cited in

(1)

• Strong subgraph k‐connectivity

This page was built for publication: Strongly connected spanning subgraph for almost symmetric networks

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