Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem

DOI10.1007/978-3-642-02882-3_7MaRDI QIDQ5323050zbMATH OpenOpenAlexFDO

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

Publication date 23 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2324/14761

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) Approximation algorithms (68W25)

Recommendations

• Approximability and inapproximability of the minimum certificate dispersal problem
• Approximability of minimum certificate dispersal with tree structures
• Parameterized certificate dispersal and its variants
• Optimal Dispersal of Certificate Chains
• Minimum certificate dispersal with tree structures
• Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
• Efficient Algorithms for Alternating Pushdown Systems with an Application to the Computation of Certificate Chains
• On mixed connectivity certificates
• A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity

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
• Optimal Dispersal of Certificate Chains
• Stabilizing Certificate Dispersal

Cited in

(6)

• Approximability and inapproximability of the minimum certificate dispersal problem
• Approximability of minimum certificate dispersal with tree structures
• Parameterized certificate dispersal and its variants
• Efficient Algorithms for Alternating Pushdown Systems with an Application to the Computation of Certificate Chains
• Minimum certificate dispersal with tree structures
• On mixed connectivity certificates

This page was built for publication: Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem

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