A tight upper bound on acquaintance time of graphs

DOI10.1007/s00373-016-1700-4zbMath1351.05211arXiv1307.6029OpenAlexW1494111593MaRDI QIDQ343701

Igor Shinkar, Omer Angel

Publication date: 29 November 2016

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.6029

zbMATH Keywords

acquaintance time of graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Collision-free network exploration ⋮ A note on the acquaintance time of random graphs ⋮ The acquaintance time of (percolated) random geometric graphs

Cites Work

• Unnamed Item
• A note on the acquaintance time of random graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• The acquaintance time of (percolated) random geometric graphs
• Acquaintance Time of Random Graphs Near Connectivity Threshold
• Acquaintance Time of a Graph
• A survey of gossiping and broadcasting in communication networks
• Routing Permutations on Graphs via Matchings
• Short Random Walks on Graphs

This page was built for publication: A tight upper bound on acquaintance time of graphs