Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees

DOI10.1007/11753728_10MaRDI QIDQ3434683zbMATH OpenOpenAlexFDO

Authors Piotr Berman, Martin Fürer, Alex Zelikovsky

Publication date 2 May 2007

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

approximation ratiomatroidparity matroid problemSteiner trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1445376
• Tighter Bounds for Graph Steiner Tree Approximation
• scientific article; zbMATH DE number 1302025
• A partition-based relaxation for Steiner trees
• New approximation algorithm for minimum Steiner tree problem

Cited in

(2)

• An augmenting path algorithm for linear matroid parity
• Algebraic algorithms for linear matroid parity problems

This page was built for publication: Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees

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