Approximability and inapproximability of the minimum certificate dispersal problem

DOI10.1016/j.tcs.2010.03.029zbMath1192.68907OpenAlexW1982007160MaRDI QIDQ982648

Tomoko Izumi, Koichi Wada, Taisuke Izumi, Hirotaka Ono

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

combinatorial optimizationgraph theoryapproximation algorithmsminimum certificate dispersal problem

Mathematics Subject Classification ID

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

Related Items (3)

Minimum Certificate Dispersal with Tree Structures ⋮ Parameterized certificate dispersal and its variants ⋮ Approximability of minimum certificate dispersal with tree structures

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• An analysis of the greedy algorithm for the submodular set covering problem
• Complexity of approximating bounded variants of optimization problems
• Algorithmic construction of sets for k -restrictions
• Provisioning a virtual private network
• Stabilizing Certificate Dispersal
• Optimal Dispersal of Certificate Chains

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