Document Open Access Logo

Isomorphism Test for Digraphs with Weighted Edges

Author Adolfo Piperno

PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.30.pdf
  • Filesize: 1.39 MB
  • 13 pages

Document Identifiers

Author Details

Adolfo Piperno
  • Dipartimento di Informatica, La Sapienza Università di Roma, Via Salaria 113, I-00198 Rome (Italy)

Cite AsGet BibTex

Adolfo Piperno. Isomorphism Test for Digraphs with Weighted Edges. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SEA.2018.30

Abstract

Colour refinement is at the heart of all the most efficient graph isomorphism software packages. In this paper we present a method for extending the applicability of refinement algorithms to directed graphs with weighted edges. We use {Traces} as a reference software, but the proposed solution is easily transferrable to any other refinement-based graph isomorphism tool in the literature. We substantiate the claim that the performances of the original algorithm remain substantially unchanged by showing experiments for some classes of benchmark graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Computing methodologies → Combinatorial algorithms
Keywords
  • Practical Graph Isomorphism
  • Weighted Directed Graphs
  • Partition Refinement

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. V.L. Arlazarov, I.I. Zuev, A.V. Uskov, and I.A. Faradzhev. An algorithm for the reduction of finite non-oriented graphs to canonical form. USSR Computational Mathematics and Mathematical Physics, 14(3):195-201, 1974. Google Scholar
  2. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 684-697, New York, NY, USA, 2016. ACM. Google Scholar
  3. Christoph Berkholz, Paul Bonsma, and Martin Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms - ESA 2013, pages 145-156. Springer Berlin Heidelberg, 2013. Google Scholar
  4. Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. Google Scholar
  5. D. G. Corneil and C. C. Gotlieb. An efficient algorithm for graph isomorphism. J. ACM, 17(1):51-64, 1970. Google Scholar
  6. Paul T. Darga, Mark H. Liffiton, Karem A. Sakallah, and Igor L. Markov. Exploiting structure in symmetry detection for cnf. In Proceedings of the 41st Annual Design Automation Conference, DAC '04, pages 530-534, New York, NY, USA, 2004. ACM. Google Scholar
  7. Paul T. Darga, Karem A. Sakallah, and Igor L. Markov. Faster symmetry discovery using sparsity of symmetries. In Proceedings of the 45th Annual Design Automation Conference, DAC '08, pages 149-154, New York, NY, USA, 2008. ACM. Google Scholar
  8. John Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Zvi Kohavi and Azaria Paz, editors, Theory of Machines and Computations, pages 189-196. Academic Press, 1971. Google Scholar
  9. Tommi Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the Meeting on Algorithm Engineering &Expermiments, pages 135-149, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. Google Scholar
  10. Tommi Junttila and Petteri Kaski. Conflict propagation and component recursion for canonical labeling. In Alberto Marchetti-Spaccamela and Michael Segal, editors, Theory and Practice of Algorithms in (Computer) Systems, pages 151-162. Springer Berlin Heidelberg, 2011. Google Scholar
  11. José Luis López-Presa, Antonio Fernández Anta, and Luis Núñez Chiroque. Conauto-2.0: Fast isomorphism testing and automorphism group computation. CoRR, abs/1108.1060, 2011. URL: http://arxiv.org/abs/1108.1060.
  12. José Luis López-Presa and Antonio Fernández Anta. Fast algorithm for graph isomorphism testing. In Jan Vahrenhold, editor, Experimental Algorithms, pages 221-232. Springer Berlin Heidelberg, 2009. Google Scholar
  13. Brendan D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45-87, 1980. Google Scholar
  14. Brendan D. McKay and Adolfo Piperno. nauty and Traces, software distribution web pages. http://cs.anu.edu.au/~bdm/nauty and URL: http://pallini.di.uniroma1.it.
  15. Brendan D. McKay and Adolfo Piperno. nauty and Traces user’s guide (version 2.6). Available at http://cs.anu.edu.au/~bdm/nauty and URL: http://pallini.di.uniroma1.it.
  16. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, ii. Journal of Symbolic Computation, 60:94-112, 2014. Google Scholar
  17. Daniel Neuen and Pascal Schweitzer. Benchmark graphs for practical graph isomorphism. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pages 60:1-60:14, 2017. Google Scholar
  18. R. Parris and Ronald C. Read. A coding procedure for graphs. Technical report, Univ. of West Indies Computer Centre, 1969. Google Scholar
  19. Adolfo Piperno. Search space contraction in canonical labeling of graphs (preliminary version). CoRR, abs/0804.4881, 2008. URL: http://arxiv.org/abs/0804.4881.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact