Minimum Certificate Dispersal with Tree Structures
From MaRDI portal
Publication:2898067
DOI10.1007/978-3-642-29952-0_51zbMath1354.68209OpenAlexW1809597216MaRDI QIDQ2898067
Hirotaka Ono, Taisuke Izumi, Koichi Wada, Tomoko Izumi
Publication date: 16 July 2012
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-29952-0_51
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- The Steiner tree problem on graphs: inapproximability results
- Approximability and inapproximability of the minimum certificate dispersal problem
- The Steiner problem with edge lengths 1 and 2
- An improved LP-based approximation for steiner tree
- Stabilizing Certificate Dispersal
- Optimal Dispersal of Certificate Chains
- The steiner problem in graphs
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs