Parameterized certificate dispersal and its variants

DOI10.1016/j.tcs.2016.02.001zbMath1335.68104OpenAlexW2263465034MaRDI QIDQ5964075

Valentin Garnero, Mathias Weller

Publication date: 26 February 2016

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

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

zbMATH Keywords

algorithmic graph theoryasymmetric cryptographyparameterized complexityTuring kernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Turing kernelization for finding long paths and cycles in restricted graph classes
• Approximability and inapproximability of the minimum certificate dispersal problem
• The point-to-point delivery and connection problems: Complexity and algorithms
• The point-to-point connection problem - analysis and algorithms
• Studying the complexity of global verification for NP-hard discrete optimization problems
• On strong distances in oriented graphs
• The Turing way to parameterized complexity
• A completeness theory for polynomial (Turing) kernelization
• Approximability of minimum certificate dispersal with tree structures
• Crown structures for vertex cover kernelization
• Parametrized complexity theory.
• A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
• Kernel(s) for problems with no kernel
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• Vertex packings: Structural properties and algorithms
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Kernelization Lower Bounds by Cross-Composition
• Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
• Graph-Theoretic Concepts in Computer Science
• Steiner Forest Orientation Problems

This page was built for publication: Parameterized certificate dispersal and its variants