On k-edge-connectivity problems with sharpened triangle inequality

DOI10.1007/3-540-44849-7_24MaRDI QIDQ4437508zbMATH OpenFDO

Authors Dirk Bongartz, Juraj Hromkovič, Ralf Klasing, Guido Proietti, Sebastian Seibert, Walter Unger, Hans-Joachim Böckenhauer

Publication date 2 December 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2653/26530189.htm

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• On k-connectivity problems with sharpened triangle inequality
• ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY
• A proof of an inequality concerning \(k\)-restricted edge connectivity
• An approximation algorithm for the minimum weight vertex-connectivity problem in complete graphs with sharpened triangle inequality.
• \(k\)-restricted edge-connectivity in triangle-free graphs
• Sharp bounds for decomposing graphs into edges and triangles
• k-edge-connectivity: approximation and LP relaxation
• On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
• On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
• Contractible edges and triangles in k-connected graphs

Cited in

(12)

• On k-connectivity problems with sharpened triangle inequality
• Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
• Subgraphs decomposable into two trees and \(k\)-edge-connected subgraphs
• On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
• Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
• k-edge-connectivity: approximation and LP relaxation
• On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
• ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY
• On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
• An approximation algorithm for the minimum weight vertex-connectivity problem in complete graphs with sharpened triangle inequality.
• On the hardness and approximation of the densest k-subgraph problem in parameterized metric graphs
• On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality

This page was built for publication: On \(k\)-edge-connectivity problems with sharpened triangle inequality

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