Minimum certificate dispersal with tree structures

DOI10.1007/978-3-642-29952-0_51MaRDI QIDQ2898067zbMATH OpenOpenAlexFDO

Authors Taisuke Izumi, Tomoko Izumi, Hirotaka Ono, Koichi Wada

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

Mathematics Subject Classification ID

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)

Recommendations

• Approximability of minimum certificate dispersal with tree structures
• Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem
• Approximability and inapproximability of the minimum certificate dispersal problem
• Parameterized certificate dispersal and its variants
• Optimal Dispersal of Certificate Chains

Cites work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An improved LP-based approximation for Steiner tree
• Approximability and inapproximability of the minimum certificate dispersal problem
• Optimal Dispersal of Certificate Chains
• Stabilizing Certificate Dispersal
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem on graphs: inapproximability results
• The steiner problem in graphs

Cited in

(6)

• scientific article; zbMATH DE number 4011953 (Why is no real title available?)
• Optimal Dispersal of Certificate Chains
• Approximability and inapproximability of the minimum certificate dispersal problem
• Approximability of minimum certificate dispersal with tree structures
• Parameterized certificate dispersal and its variants
• Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem

This page was built for publication: Minimum certificate dispersal with tree structures

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