Article

Free access

Matching nuts and bolts in O(n log n) time

Authors:

János Komlós,

Yuan Ma,

Endre SzemerédiAuthors Info & Claims

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

Pages 232 - 241

Published: 28 January 1996 Publication History

PDF eReader

References

[1]

M. Ajtai, J. KomlSs, W. L. Steiger, and E. Szemer~di. Optimal parallel selection has complexity O(log log N). Journal of Computer and System Sciences, 38(1):125-133, 1989. The conference version appears in Proceedings of the I8th Annual A CM Symposium on ~he Theory of Computing, pages 188-195, 1986.

Digital Library

Google Scholar

[2]

M. Ajtai, J. Koml6s, and E. Szemer~di. Sorting in c logn parallel steps. Combinatorica, 3(1):1-19, 1983. See also the conference version, which appears in Proceedings of ~he 15th Annual A CM Symposium on the Theory of Computing, pages 1-9, May 1983.

Digital Library

Google Scholar

[3]

N. Alon, M. Blum, A. Fiat, S. Kannan, M. Naor, and R. Ostrovsky. Matching nuts and bolts. In Proceedings of the 5th Annual A CM-$IAM Symposium on Discrete Algorithms, pages 690-696, January 1994.

Digital Library

Google Scholar

[4]

Y. Aumann. Personal communication. 1994.

Google Scholar

[5]

M. Blum, R. Floyd, V. Pratt, tL. Rivest, and R. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7:448-461, 1973.

Google Scholar

[6]

P. Bradford and R. Fleischer. Matching nuts and bolts faster. Technical Report MPI-I-95-1-003, Max-Planck-Institut Ffir Informa~ik, May 1995. An updated version appears in Proceedings of the $izth International Symposium oa Algorithms and Computation (ISAAC '95).

Digital Library

Google Scholar

[7]

M. S. Paterson. Improved sorting networks with O(log N) depth. Algorithmica, 5:75-92, 1990.

Google Scholar

[8]

O. g. E. Rawlins. Compared to what? an introduction to the analysis of algorithms. Computer Science Press, 1991.

Digital Library

Google Scholar

[9]

L. G. Valiant. Parallelism in comparison problems. S~AM J. Comput., 4:348-355, 1975.

Google Scholar

Cited By

View all

IV AWenk C(2010)Geodesic Fréchet distance inside a simple polygonACM Transactions on Algorithms10.1145/1868237.18682477:1(1-19)Online publication date: 8-Dec-2010
https://dl.acm.org/doi/10.1145/1868237.1868247
Kannan SKhanna S(2003)Selection with monotone comparison costsProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644111(10-17)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644111
Charikar MFagin RGuruswami VKleinberg JRaghavan PSahai AYao FLuks E(2000)Query strategies for priced information (extended abstract)Proceedings of the thirty-second annual ACM symposium on Theory of computing10.1145/335305.335382(582-591)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/335305.335382

Index Terms

Matching nuts and bolts in O(n log n) time
1. Mathematics of computing
  1. Discrete mathematics
  2. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching
  2. Randomness, geometry and discrete structures

Recommendations

Matching Nuts and Bolts in O(n log n) Time

Given a set of n nuts of distinct widths and a set of n bolts such that each nut corresponds to a unique bolt of the same width, how should we match every nut with its corresponding bolt by comparing nuts with bolts? (No comparison is allowed between ...
Matching nuts and bolts faster
Fully Dynamic Maximal Matching in $O(\log n)$ Update Time

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized $O(\log n)$ time for each edge update, where $n$ is the number of vertices in the graph. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

January 1996

586 pages

ISBN:0898713668

Chairman:
Éva Tardos

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 28 January 1996

Check for updates

Qualifiers

Article

Conference

SODA96

Sponsor:

SIGACT
SIAM

SODA96: Conference on Discrete Algorithms

January 28 - 30, 1996

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
856
Total Downloads

Downloads (Last 12 months)86
Downloads (Last 6 weeks)15

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

IV AWenk C(2010)Geodesic Fréchet distance inside a simple polygonACM Transactions on Algorithms10.1145/1868237.18682477:1(1-19)Online publication date: 8-Dec-2010
https://dl.acm.org/doi/10.1145/1868237.1868247
Kannan SKhanna S(2003)Selection with monotone comparison costsProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644111(10-17)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644111
Charikar MFagin RGuruswami VKleinberg JRaghavan PSahai AYao FLuks E(2000)Query strategies for priced information (extended abstract)Proceedings of the thirty-second annual ACM symposium on Theory of computing10.1145/335305.335382(582-591)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/335305.335382

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Matching Nuts and Bolts in O(n log n) Time

Matching nuts and bolts faster

Fully Dynamic Maximal Matching in $O(\log n)$ Update Time