Approximability of minimum certificate dispersal with tree structures

DOI10.1016/J.TCS.2015.01.007MaRDI QIDQ2354400zbMATH OpenOpenAlexFDO

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

Publication date 13 July 2015

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

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

zbMATH Keywords

approximabilityminimum certificate dispersal problemtree structure

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• 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 in graphs
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem on graphs: inapproximability results

Cited in

(8)

• Trust-based hexagonal clustering for efficient certificate management scheme in mobile ad hoc networks
• Minimum certificate dispersal with tree structures
• Efficient Algorithms for Alternating Pushdown Systems with an Application to the Computation of Certificate Chains
• scientific article; zbMATH DE number 4011953 (Why is no real title available?)
• Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem
• Optimal Dispersal of Certificate Chains
• Parameterized certificate dispersal and its variants
• Approximability and inapproximability of the minimum certificate dispersal problem

Describes a project that uses

Uses Software

• BATON

This page was built for publication: Approximability of 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 Q2354400)