Minmax strongly connected subgraphs with node penalties

DOI10.1155/JAMDS.2005.107zbMATH Open1141.05339MaRDI QIDQ930773FDOQ930773

Abraham P. Punnen

Publication date: 1 July 2008

Published in: Journal of Applied Mathematics and Decision Sciences (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/129084

Recommendations

• Approximating the minimum strongly connected subgraph via a matching lower bound
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• scientific article; zbMATH DE number 1003248
• Computing Minimal Spanning Subgraphs in Linear Time
• Approximating the Minimum Equivalent Digraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Cited In (2)

• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• The minimum spanning strong subdigraph problem is fixed parameter tractable

This page was built for publication: Minmax strongly connected subgraphs with node penalties

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