Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model

DOI10.1007/978-3-319-25258-2_26zbMath1471.68198OpenAlexW2295809089WikidataQ62045897 ScholiaQ62045897MaRDI QIDQ3460729

Jarkko Peltomäki, Ivan Rapaport, Jarkko Kari, Martin Matamala

Publication date: 8 January 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-25258-2_26

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Network protocols (68M12) Games on graphs (graph-theoretic aspects) (05C57) Communication complexity, information complexity (68Q11)

Related Items (5)

Graph reconstruction in the congested clique ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Fast distributed algorithms for testing graph properties ⋮ The Impact of Locality in the Broadcast Congested Clique Model ⋮ The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model

Cites Work

• Unnamed Item
• Excluding pairs of graphs
• Graph minors. XX: Wagner's conjecture
• Lower bound of the Hadwiger number of graphs by their average degree
• Complement reducible graphs
• On randomized one-round communication complexity
• When distributed computation is communication expensive
• Cycles of even length in graphs
• The extremal function for complete minors
• On a property of the class of n-colorable graphs
• Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy
• The communication complexity of distributed task allocation
• On the power of the congested clique model
• Distributedly Testing Cycle-Freeness
• An extremal function for contractions of graphs
• Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
• Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
• The Simultaneous Number-in-Hand Communication Model for Networks: Private Coins, Public Coins and Determinism

This page was built for publication: Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model