Article

Free access

Reinventing the wheel: an optimal data structure for connectivity queries

Authors:

Robert F. Cohen,

Giuseppe Di Battista,

Arkady Kanevsky,

Roberto TamassiaAuthors Info & Claims

STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing

Pages 194 - 200

https://doi.org/10.1145/167088.167152

Published: 01 June 1993 Publication History

PDF eReader

References

[1]

G. Di Battista and R. Tamassia, 'COn-Line Graph Algorithms with SPQR-Trees," Automata, Languages and Programming (Proc. 17th ICALP), Lecture Notes in Computer Science 442(1990), 598-611.

Digital Library

Google Scholar

[2]

A. Kanevsky, "On the Number of Minimum Size Separating Vertex Sets in a Graph and How to Find All of Them," Proc. 1st Annual ACM-SIAM Syrup. on Discrete Algorithms(1990), 411-421.

Digital Library

Google Scholar

[3]

A. Kanevsky, R. Tamassia, J. Chen, and G. Di Battista, "On-Line Maintenance of the Four- Connected Components of a Graph," Proc. 32th IEEE Symp. on Foundations of Computer Science (1991), 793-801.

Digital Library

Google Scholar

[4]

A.V. Karzanov and E.A. Timofeev, "Efficient Algorithm for Finding all Minimal Edge Cuts of a Nonoriented Graph," Cybernetics 2, 1986.

Google Scholar

[5]

K. Menger, "Zur Allgemeinen Kurventheorie," Fund. Math. 10(1927), 96-115.

Crossref

Google Scholar

[6]

D. Naor, D. Gusfield, and C. Martel, "A Fast Algorithm for Optimally increasing the Edge- Connectivity," Proc. IEEE Syrup. on Foundations of Computer Science (1990), 698-707.

Google Scholar

[7]

R. Tamassia, "A Dynamic Data Structure for Planar Graph Embedding," Automata, Languages and Programming (Proc. 15th ICALP), Lecture Notes in Computer Science 317 (1988), 576-590.

Digital Library

Google Scholar

[8]

R.E. Tarjan and A.C.-C. Yao, "Storing a Sparse Table," Communications of the ACM 22 (1979), 606-611.

Digital Library

Google Scholar

[9]

J. Westbrook and R.E. Tarjan, "Maintaining Bridge-Connected and Bieonnected Components On-Line," A1gorithmica 7 (1992), 433-464.

Google Scholar

Cited By

View all

Di Battista GTamassia RVismara L(2005)Output-sensitive reporting of disjoint paths (extended abstract)Computing and Combinatorics10.1007/3-540-61332-3_141(81-91)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-61332-3_141
Chiang YLin CLu HKosaraju S(2001)Orderly spanning trees with applications to graph encoding and graph drawingProceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms10.5555/365411.365518(506-515)Online publication date: 9-Jan-2001
https://dl.acm.org/doi/10.5555/365411.365518
Damiani ETanca L(2001)Blind Queries to XML DataDatabase and Expert Systems Applications10.1007/3-540-44469-6_32(345-356)Online publication date: 28-Jun-2001
https://doi.org/10.1007/3-540-44469-6_32
Show More Cited By

Index Terms

Reinventing the wheel: an optimal data structure for connectivity queries

Recommendations

Reinventing the Wheel: Transforming Steering Wheel Systems for Autonomous Vehicles
UIST '17: Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology

In this paper, we introduce two different transforming steering wheel systems that can be utilized to augment user experience for future partially autonomous and fully autonomous vehicles. The first one is a robotic steering wheel that can mechanically ...
Reinventing the Wheel

To prevent rollover accidents, new cars sold in the United States since 2004 have been outfitted with tire-pressure monitors that warn the driver when tires are going flat. But the battery-powered initial version of the technology has proved expensive. ...
Reinventing the wheel, revisited

I am a cyclist. I've ridden since before my paper route at age twelve; I rode to high school; and for 12 years I rode to work. I no longer ride to work, but I try to ride about an hour a day. In all those years I never really paid much attention to my ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing

June 1993

812 pages

ISBN:0897915917

DOI:10.1145/167088

Chairmen:
Rao Kosaraju
John Hopkins Univ., Baltimore, MD
,
David Johnson
AT&T Bell Lab.
,
Alok Aggarwal
IBM T. J. Watson Research Center,Yorktown Heights, NY

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC93

Sponsor:

SIGACT

STOC93: 25th Annual ACM Symposium on the Theory of Computing

May 16 - 18, 1993

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
481
Total Downloads

Downloads (Last 12 months)89
Downloads (Last 6 weeks)24

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Di Battista GTamassia RVismara L(2005)Output-sensitive reporting of disjoint paths (extended abstract)Computing and Combinatorics10.1007/3-540-61332-3_141(81-91)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-61332-3_141
Chiang YLin CLu HKosaraju S(2001)Orderly spanning trees with applications to graph encoding and graph drawingProceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms10.5555/365411.365518(506-515)Online publication date: 9-Jan-2001
https://dl.acm.org/doi/10.5555/365411.365518
Damiani ETanca L(2001)Blind Queries to XML DataDatabase and Expert Systems Applications10.1007/3-540-44469-6_32(345-356)Online publication date: 28-Jun-2001
https://doi.org/10.1007/3-540-44469-6_32
Fernandez RKanevsky A(1994)Generalized ring interconnection networksProceedings of 8th International Parallel Processing Symposium10.1109/IPPS.1994.288322(30-34)Online publication date: 1994
https://doi.org/10.1109/IPPS.1994.288322

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

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

Reinventing the Wheel: Transforming Steering Wheel Systems for Autonomous Vehicles

Reinventing the Wheel

Reinventing the wheel, revisited