Communication complexity of pairs of graph families with applications

DOI10.4230/LIPICS.MFCS.2017.13MaRDI QIDQ5111227zbMATHOpenAlexFDO

Authors Sudeshna Kolay, Fahad Panolan, Saket Saurabh

Publication date 26 May 2020

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

zbMATH Keywords

communication complexityseparating familyFPT-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)

Recommendations

• Communication complexity and graph families
• scientific article; zbMATH DE number 6292585
• Some improved bounds on communication complexity via new decomposition of cliques
• On covering graphs by complete bipartite subgraphs
• The communication complexity of enumeration, elimination, and selection

Cites work

• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 7204504 (Why is no real title available?)
• scientific article; zbMATH DE number 4197419 (Why is no real title available?)
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• A note on non-deterministic communication complexity with few witnesses
• Clique versus independent set
• Communication Complexity
• Complexity of graph partition problems
• Deterministic communication vs. partition number
• Expressing combinatorial optimization problems by linear programs
• Ordered biclique partitions and communication complexity problems
• Parameterized algorithms
• Some improved bounds on communication complexity via new decomposition of cliques
• Stable sets and polynomials
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms

Cited in

(2)

• Communication complexity and graph families
• Communication complexity in vertex partition whiteboard model

This page was built for publication: Communication complexity of pairs of graph families with applications

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