Approximability and inapproximability of the minimum certificate dispersal problem

DOI10.1016/J.TCS.2010.03.029MaRDI QIDQ982648zbMATH OpenOpenAlexFDO

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

Publication date 7 July 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.03.029

zbMATH Keywords

approximation algorithmscombinatorial optimizationgraph theoryminimum certificate dispersal problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

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

Cites work

• Algorithmic construction of sets for k -restrictions
• An analysis of the greedy algorithm for the submodular set covering problem
• Complexity of approximating bounded variants of optimization problems
• scientific article; zbMATH DE number 5485556 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the complexity of H-coloring
• Optimal Dispersal of Certificate Chains
• Provisioning a virtual private network: a network design problem for multicommodity flow
• Stabilizing Certificate Dispersal

Cited in

(5)

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

This page was built for publication: Approximability and inapproximability of the minimum certificate dispersal problem

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