Minimum vertex cover, distributed decision-making, and communication complexity

DOI10.1007/3-540-59071-4_43zbMath1528.68282MaRDI QIDQ6184364

Pierluigi Crescenzi, Luca Trevisan

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Probabilistic communication complexity
• Information Transfer under Different Sets of Protocols
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Solving Undirected Graph Problems on VLSI
• Reducibility among Combinatorial Problems
• Linear programming without the matrix
• On the value of information in distributed decision-making (extended abstract)