article

The diameter of a cycle plus a random matching

Authors:

B. Bollobás,

F. R. K. ChungAuthors Info & Claims

SIAM Journal on Discrete Mathematics, Volume 1, Issue 3

Pages 328 - 333

https://doi.org/10.1137/0401033

Published: 01 August 1988 Publication History

Abstract

No abstract available.

Cited By

View all

Capalbo M(2021)An Explicit Infinite Family of -Vertex Graphs with Maximum Degree K and Diameter for Each K − 1 a Prime PowerCombinatorica10.1007/s00493-020-3989-041:3(353-378)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s00493-020-3989-0
Capalbo MCharikar MCohen E(2019)Explicit 𝑁-vertex graphs with maximum degree 𝐾 and diameter [1+𝑜(1)]log𝐾-1 𝑁 for each 𝐾-1 a prime powerProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316399(1191-1202)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316399
Ma LSrivatsa MCansever DYan XKase SVanni M(2019)Performance Bounds of Decentralized Search in Expert Networks for Query AnsweringACM Transactions on Knowledge Discovery from Data10.1145/330023013:2(1-23)Online publication date: 13-Mar-2019
https://dl.acm.org/doi/10.1145/3300230
Show More Cited By

Index Terms

The diameter of a cycle plus a random matching

Recommendations

The Diameter of Sparse Random Graphs

We consider the diameter of a random graph G(n,p) for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. ...
Diameter and broadcast time of random geometric graphs in arbitrary dimensions
ISAAC'11: Proceedings of the 22nd international conference on Algorithms and Computation

A random geometric graph (RGG) is defined by placing n points uniformly at random in [0, n ^{1/ d}]^d, and joining two points by an edge whenever their Euclidean distance is at most some fixed r . We assume that r is larger than the critical ...
Matching Random Colored Points with Rectangles
WALCOM: Algorithms and Computation
Abstract
Let be a set of n points, randomly and uniformly selected. Let be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random variable M(n) equal to the number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Discrete Mathematics

SIAM Journal on Discrete Mathematics Volume 1, Issue 3

Aug. 1988

142 pages

ISSN:0895-4801

Editor:
W. T. Trotter

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 August 1988

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Capalbo M(2021)An Explicit Infinite Family of -Vertex Graphs with Maximum Degree K and Diameter for Each K − 1 a Prime PowerCombinatorica10.1007/s00493-020-3989-041:3(353-378)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s00493-020-3989-0
Capalbo MCharikar MCohen E(2019)Explicit 𝑁-vertex graphs with maximum degree 𝐾 and diameter [1+𝑜(1)]log𝐾-1 𝑁 for each 𝐾-1 a prime powerProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316399(1191-1202)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316399
Ma LSrivatsa MCansever DYan XKase SVanni M(2019)Performance Bounds of Decentralized Search in Expert Networks for Query AnsweringACM Transactions on Knowledge Discovery from Data10.1145/330023013:2(1-23)Online publication date: 13-Mar-2019
https://dl.acm.org/doi/10.1145/3300230
Yasudo RKoibuchi MNakano KMatsutani HAmano H(2019)Designing High-Performance Interconnection Networks with Host-Switch GraphsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.286428630:2(315-330)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TPDS.2018.2864286
Katsikarelis ILampis MPaschos V(2019)Improved (In-)Approximability Bounds for d-Scattered SetApproximation and Online Algorithms10.1007/978-3-030-39479-0_14(202-216)Online publication date: 12-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-39479-0_14
Gao JSchoenebeck GYu F(2017)Cascades and Myopic Routing in Nonhomogeneous Kleinberg’s Small World ModelWeb and Internet Economics10.1007/978-3-319-71924-5_27(383-394)Online publication date: 17-Dec-2017
https://dl.acm.org/doi/10.1007/978-3-319-71924-5_27
Fujiwara IKoibuchi MMatsutani HCasanova H(2015)Swap-And-Randomize: A Method for Building Low-Latency HPC InterconnectsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.234086326:7(2051-2060)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1109/TPDS.2014.2340863
Dabrowski C(2015)Catastrophic event phenomena in communication networksComputer Science Review10.1016/j.cosrev.2015.10.00118:C(10-45)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.cosrev.2015.10.001
Friedrich TKrohmer A(2015)On the Diameter of Hyperbolic Random GraphsProceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 913510.1007/978-3-662-47666-6_49(614-625)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-662-47666-6_49
Le Nhat TNguyen TNguyen K(2014)Robust and Efficient Custom Routing for Interconnection Networks with Distributed ShortcutsInternational Journal of Distributed Systems and Technologies10.4018/ijdst.20141001045:4(51-74)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.4018/ijdst.2014100104
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

The Diameter of Sparse Random Graphs

Diameter and broadcast time of random geometric graphs in arbitrary dimensions

Matching Random Colored Points with Rectangles

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations