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

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

zbMATH Keywords

algorithmmatroid intersectionnetwork connectivity

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Cites Work

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

Cited In (5)

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

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)