article

Free access

A versatile data structure for edge-oriented graph algorithms

Author:

Jürgen EbertAuthors Info & Claims

Communications of the ACM, Volume 30, Issue 6

Pages 513 - 519

https://doi.org/10.1145/214762.214769

Published: 01 June 1987 Publication History

PDF eReader

Abstract

An abstract graph module that allows for easy and secure programming of a great number of graph algorithms is implemented by symmetrically stored forward and backward adjacency lists, thus supporting edge-oriented traversals of general directed and undirected graphs.

References

[1]

Berge. C. Graphs and Hypergraphs. North-Holland, Amsterdam, 1973. A textbook on graph theory.

Digital Library

Google Scholar

[2]

Ebert. J. Effiziente Graphenalgorithmen. Aula, Wiesbaden. West Germany. 1981. A textbook on graph algorithms and their implementation in Algal-like languages using abstract data and refinements.

Google Scholar

[3]

Ebert, J. Implementing a functional language on a vom Neumann computer. Tech. Rep. 3/&i, EWH Koblenz, Fachbericht Informatik, Mar. 1985. A report on an implementation technique for functional languages using attributed and ordered directed graphs.

Google Scholar

[4]

Even, S. Graph Algorithms. Pitman, Marshfield, Mass., 1979. A textbook on graph theory featuring algorithms.

Digital Library

Google Scholar

[5]

Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969. A textbook on graph theory.

Google Scholar

[6]

Tarjan, R.E. Depth-first search and linear graph algorithms. SIAM J. Comput. I, 2 (1972). 146-160. A fundamental paper showing that some connectivity problems are solvable in linear time using depthfirst search on adjacency-list representations of graphs.

Google Scholar

Cited By

View all

Zhang KTang LZhong SLuo HZhao C(2023)Perfect Hash-Based Routing Lookup for LEO Constellation Backbone NetworkIEEE Transactions on Aerospace and Electronic Systems10.1109/TAES.2023.3244897(1-15)Online publication date: 2023
https://doi.org/10.1109/TAES.2023.3244897
Veselý PKavička AKrýže P(2023)Automated Construction of Mesoscopic Railway Infrastructure Models Supporting Station Throat Capacity AssessmentIEEE Access10.1109/ACCESS.2023.326681311(37869-37899)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3266813
Kavička AKrýže P(2021)Dynamic Automated Search of Shunting Routes within Mesoscopic Rail-Traffic SimulatorsJournal of Advanced Transportation10.1155/2021/88405162021(1-22)Online publication date: 5-Apr-2021
https://doi.org/10.1155/2021/8840516
Show More Cited By

Index Terms

A versatile data structure for edge-oriented graph algorithms
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Collapsible subgraphs of a 4-edge-connected graph
Abstract
Jaeger in 1979 showed that every 4-edge-connected graph is supereulerian, graphs that have spanning eulerian subgraphs. Catlin in 1988 sharpened Jaeger’s result by showing that every 4-edge-connected graph is collapsible, graphs that are ...
Graph edge colouring: Tashkinov trees and Goldberg's conjecture

For the chromatic index @g^'(G) of a (multi)graph G, there are two trivial lower bounds, namely the maximum degree @D(G) and the density W(G)=max"H"@__ __"G","|"V"("H")"|">="2@__ __|E(H)|/@__ __|V(H)|/2@__ __@__ __. A famous conjecture due to Goldberg [...
Rainbow matchings in an edge-colored planar bipartite graph
Highlights
- Given an edge-colored graph G, if any two edges of G receive distinct colors, then we call G a rainbow graph. The anti-Ramsey number AR(G;H) is the maximum ...
Abstract
In this paper, we consider the existence of rainbow matchings in maximal bipartite planar graphs. We determine the maximum number of colors appearing in an edge-coloring of maximal bipartite planar graphs with a Hamilton cycle which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 30, Issue 6

June 1987

92 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/214762

Editor:
Peter J. Denning

Issue’s Table of Contents

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 1987

Published in CACM Volume 30, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
1,209
Total Downloads

Downloads (Last 12 months)212
Downloads (Last 6 weeks)26

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang KTang LZhong SLuo HZhao C(2023)Perfect Hash-Based Routing Lookup for LEO Constellation Backbone NetworkIEEE Transactions on Aerospace and Electronic Systems10.1109/TAES.2023.3244897(1-15)Online publication date: 2023
https://doi.org/10.1109/TAES.2023.3244897
Veselý PKavička AKrýže P(2023)Automated Construction of Mesoscopic Railway Infrastructure Models Supporting Station Throat Capacity AssessmentIEEE Access10.1109/ACCESS.2023.326681311(37869-37899)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3266813
Kavička AKrýže P(2021)Dynamic Automated Search of Shunting Routes within Mesoscopic Rail-Traffic SimulatorsJournal of Advanced Transportation10.1155/2021/88405162021(1-22)Online publication date: 5-Apr-2021
https://doi.org/10.1155/2021/8840516
Valiente GValiente G(2021)IntroductionAlgorithms on Trees and Graphs10.1007/978-3-030-81885-2_1(3-43)Online publication date: 12-Oct-2021
https://doi.org/10.1007/978-3-030-81885-2_1
Ge LLiu WShan J(2017)Development and Application of a New High-Efficiency Sparse Linear System Solver in the Thermal-Hydraulic System Analysis CodeScience and Technology of Nuclear Installations10.1155/2017/70721972017(1-10)Online publication date: 2017
https://doi.org/10.1155/2017/7072197
Januario TUrrutia SRibeiro Cde Werra D(2016)Edge coloring: A natural model for sports schedulingEuropean Journal of Operational Research10.1016/j.ejor.2016.03.038254:1(1-8)Online publication date: Oct-2016
https://doi.org/10.1016/j.ejor.2016.03.038
Roughan MTuke J(2015)The Hitchhikers Guide to Sharing Graph DataProceedings of the 2015 3rd International Conference on Future Internet of Things and Cloud10.1109/FiCloud.2015.76(435-442)Online publication date: 24-Aug-2015
https://dl.acm.org/doi/10.1109/FiCloud.2015.76
Stoica FStoica L(2013)Building a new CTL model checker using Web services2013 21st International Conference on Software, Telecommunications and Computer Networks - (SoftCOM 2013)10.1109/SoftCOM.2013.6671858(1-5)Online publication date: Sep-2013
https://doi.org/10.1109/SoftCOM.2013.6671858
Botelho FPagh RZiviani N(2013)Practical perfect hashing in nearly optimal spaceInformation Systems10.1016/j.is.2012.06.00238:1(108-131)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.is.2012.06.002
Alves THage JRademaker P(2011)A Comparative Study of Code Query TechnologiesProceedings of the 2011 IEEE 11th International Working Conference on Source Code Analysis and Manipulation10.1109/SCAM.2011.14(145-154)Online publication date: 25-Sep-2011
https://dl.acm.org/doi/10.1109/SCAM.2011.14
Show More Cited By

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.

Abstract

References

Cited By

Index Terms

Recommendations

Collapsible subgraphs of a 4-edge-connected graph

Graph edge colouring: Tashkinov trees and Goldberg's conjecture

Rainbow matchings in an edge-colored planar bipartite graph

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations