Communication Complexity of Pairs of Graph Families with Applications

DOI10.4230/LIPIcs.MFCS.2017.13zbMath1441.68052OpenAlexW2774463688MaRDI QIDQ5111227

Fahad Panolan, Sudeshna Kolay, Saket Saurabh

Publication date: 26 May 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.13

zbMATH Keywords

separating familycommunication complexityFPT-algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique versus independent set
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• Expressing combinatorial optimization problems by linear programs
• Stable sets and polynomials
• A note on non-deterministic communication complexity with few witnesses
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• Ordered biclique partitions and communication complexity problems
• Some improved bounds on communication complexity via new decomposition of cliques
• Complexity of graph partition problems
• Deterministic Communication vs. Partition Number
• Communication Complexity
• Parameterized Algorithms