Polynomial time algorithms for edge-connectivity augmentation of Hamiltonian paths

DOI10.1007/3-540-45678-3_30MaRDI QIDQ4474101zbMATH OpenFDO

Authors A. Galluccio, Guido Proietti

Publication date 4 August 2004

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/2223/22230345.htm

zbMATH Keywords

2-edge connectivityaugmentationHamiltonian pathnetwork survivability

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Communication networks in operations research (90B18)

Recommendations

• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• Graph-Theoretic Concepts in Computer Science
• A faster approximation algorithm for 2-edge-connectivity augmentation
• Approximation algorithms for graph augmentation
• Approximation Algorithms for Graph Augmentation

Cited in

(5)

• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• The Hamiltonian Augmentation Problem and Its Applications to Graph Drawing
• Graph-Theoretic Concepts in Computer Science
• Approximation and Online Algorithms
• On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality

This page was built for publication: Polynomial time algorithms for edge-connectivity augmentation of Hamiltonian paths

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