The k-path tree matroid and its applications to survivable network design

DOI10.1016/J.DISOPT.2006.11.009zbMATH Open1177.90049OpenAlexW2089655957MaRDI QIDQ951105FDOQ951105

Authors Esther M. Arkin, Refael Hassin

Publication date 29 October 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2006.11.009

zbMATH Keywords

algorithmmatroid intersectionnetwork connectivity

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Recommendations

• scientific article; zbMATH DE number 1263260
• Fast exact algorithms for survivable network design with uniform requirements
• An efficient approximation algorithm for the survivable network design problem
• Inapproximability of Survivable Networks
• On survivable network polyhedra

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3661345 (Why is no real title available?)
• scientific article; zbMATH DE number 3614523 (Why is no real title available?)
• scientific article; zbMATH DE number 795223 (Why is no real title available?)
• scientific article; zbMATH DE number 3301261 (Why is no real title available?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• A note on relatives to the Held and Karp 1-tree problem
• Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems
• Algorithms for a network design problem with crossing supermodular demands
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connectivity-splitting models for survivable network design
• Design of Survivable Networks: A survey
• Designing hierarchical survivable networks
• Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems
• Network flows. Theory, algorithms, and applications.
• On the point-to-point connection problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The directed subgraph homeomorphism problem
• The point-to-point connection problem - analysis and algorithms
• The point-to-point delivery and connection problems: Complexity and algorithms

Cited in

(5)

• \(k\)-trails: recognition, complexity, and approximations
• Approximate integer decompositions for undirected network design problems
• The parameterized complexity of the survivable network design problem
• \(k\)-trails: recognition, complexity, and approximations
• Rooted \(k\)-connections in digraphs

This page was built for publication: The \(k\)-path tree matroid and its applications to survivable network design

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