A Tight Upper Bound on Acquaintance Time of Graphs

Omer Angel, Igor Shinkar

Type: Article

Publication Date: 2016-04-02

Citations: 6

DOI: https://doi.org/10.1007/s00373-016-1700-4

View Publication

Download PDF

Locations

Graphs and Combinatorics - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	A Tight Upper Bound on Acquaintance Time of Graphs	2013	Omer Angel Igor Shinkar
+	A Tight Upper Bound on Acquaintance Time of Graphs	2013	Omer Angel Igor Shinkar
+	Domination number of the acquaint vertex gluing of graphs	2014	Michael Magbanua Bacolod Michael P. Baldado
+ PDF Chat	Almost Tight Bounds for Online Hypergraph Matching	2024	Thorben Tröbst Rajan Udwani
+	Bandwidth on AT-free graphs	2011	Petr A. Golovach Pinar Heggernes Dieter Kratsch Daniel Lokshtanov Daniel Meister Saket Saurabh
+	From acquaintance to best friend forever : robust and fine-grained inference of social-tie strengths	2018	Florian Adriaens Tijl De Bie Aristides Gionis Jefrey Lijffijt Polina Rozenshtein
+	Some formulas and bounds for the bandwidth of graphs	1999	Yvette F. Lim
+	From acquaintance to best friend forever: robust and fine-grained inference of social tie strengths.	2018	Florian Adriaens Tijl De Bie Aristides Gionis Jefrey Lijffijt Polina Rozenshtein
+ PDF Chat	Maximum Betweenness Centrality: Approximability and Tractable Cases	2011	Martin Fink Joachim Spoerhase
+	Independence and average distance in graphs	1997	Peter A. Firby Julie Haviland
+	A digraph version of the Friendship Theorem	2024	Myungho Choi Hojin Chu Suh-Ryung Kim
+	Tree-depth, subgraph coloring and homomorphism bounds	2005	Jaroslav Nešetřil Patrice Ossona de Mendez
+	Spanning tree with lower bound on the degrees	2017	Zoltán Király
+	Lower and upper bounds on graph communicabilities	2024	Amir Hossein Ghodrati Mohammad Ali Hosseinzadeh
+ PDF Chat	Lower Bounds for the Graph Homomorphism Problem	2015	Fedor V. Fomin Alexander Golovnev Alexander S. Kulikov Ivan Mihajlin
+	Graphs with small distance-based complexities	2023	Modjtaba Ghorbani Zahra Vaziri
+	A LOWER BOUND ON WAIT-FREE	1993	Safiya Moran Gadi Taubenfeld
+	Algorithmes et applications pour la coloration et les alliances dans les graphes	2013	Saïd Yahiaoui
+	On the time to traverse all edges of a graph	1991	David Zuckerman
+	A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs	1999	LaiYung-Ling WilliamsKenneth

Works That Cite This (4)

Action	Title	Year	Authors
+	The acquaintance time of (percolated) random geometric graphs	2015	Tobias Müller Paweł Prałat
+	Sorting Networks On Restricted Topologies	2016	Indranil Banerjee Dana Richards Igor Shinkar
+ PDF Chat	A Note on the Acquaintance Time of Random Graphs	2013	William B. Kinnersley Dieter Mitsche Paweł Prałat
+ PDF Chat	Sorting Networks on Restricted Topologies	2019	Indranil Banerjee Dana Richards Igor Shinkar

Works Cited by This (6)

Action	Title	Year	Authors
+	Acquaintance time of random graphs near connectivity threshold	2014	Andrzej Dudek Paweł Prałat
+ PDF Chat	A Note on the Acquaintance Time of Random Graphs	2013	William B. Kinnersley Dieter Mitsche Paweł Prałat
+ PDF Chat	Short Random Walks on Graphs	1996	Greg Barnes Uriel Feige
+ PDF Chat	Routing Permutations on Graphs via Matchings	1994	Noga Alon Fan Chung Ron Graham
+	The acquaintance time of (percolated) random geometric graphs	2015	Tobias Müller Paweł Prałat
+	Limit distribution for the existence of hamiltonian cycles in a random graph	1983	János Komlós Endre Szemerédi