Better algorithms for minimum weight vertex-connectivity problems

DOI10.1007/BFB0023488MaRDI QIDQ5048953zbMATH OpenOpenAlexFDO

Authors V. Auletta, Mimmo Parente

Publication date 9 November 2022

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

Full work available at URL https://doi.org/10.1007/bfb0023488

Mathematics Subject Classification ID

Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Publication:4886063
• An approximation algorithm for minimum-cost vertex-connectivity problems
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• An approximation algorithm for the minimum weight vertex-connectivity problem in complete graphs with sharpened triangle inequality.
• Algorithms for the constrained maximum-weight connected graph problem
• Algorithms for the minimum weight k-fold (connected) dominating set problem
• A better subgraph of the minimum weight triangulation
• Approximation algorithms for connected graph factors of minimum weight
• scientific article; zbMATH DE number 1817738

Cites work

• An application of submodular flows
• Approximation Algorithms for Graph Augmentation
• Augmentation Problems
• scientific article; zbMATH DE number 437545 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263175 (Why is no real title available?)
• scientific article; zbMATH DE number 910889 (Why is no real title available?)
• On the relationship between the biconnectivity augmentation and traveling salesman problems

Cited in

(11)

• Faster approximation algorithms for weighted triconnectivity augmentation problems
• Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
• scientific article; zbMATH DE number 1817738 (Why is no real title available?)
• Pruning 2-connected graphs
• On the Structure of Minimum-Weight k-Connected Spanning Networks
• scientific article; zbMATH DE number 1305527 (Why is no real title available?)
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
• Improved Approximation Algorithms for Uniform Connectivity Problems
• A better subgraph of the minimum weight triangulation
• An approximation algorithm for minimum-cost vertex-connectivity problems

This page was built for publication: Better algorithms for minimum weight vertex-connectivity problems

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