2 Search Results for "Piperno, Adolfo"

Document
DOI: 10.4230/LIPIcs.ESA.2021.6
Parallel Computation of Combinatorial Symmetries

Authors: Markus Anders and Pascal Schweitzer

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
In practice symmetries of combinatorial structures are computed by transforming the structure into an annotated graph whose automorphisms correspond exactly to the desired symmetries. An automorphism solver is then employed to compute the automorphism group of the constructed graph. Such solvers have been developed for over 50 years, and highly efficient sequential, single core tools are available. However no competitive parallel tools are available for the task. We introduce a new parallel randomized algorithm that is based on a modification of the individualization-refinement paradigm used by sequential solvers. The use of randomization crucially enables parallelization. We report extensive benchmark results that show that our solver is competitive to state-of-the-art solvers on a single thread, while scaling remarkably well with the use of more threads. This results in order-of-magnitude improvements on many graph classes over state-of-the-art solvers. In fact, our tool is the first parallel graph automorphism tool that outperforms current sequential tools.
Cite as

Markus Anders and Pascal Schweitzer. Parallel Computation of Combinatorial Symmetries. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{anders_et_al:LIPIcs.ESA.2021.6,
  author =	{Anders, Markus and Schweitzer, Pascal},
  title =	{{Parallel Computation of Combinatorial Symmetries}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.6},
  URN =		{urn:nbn:de:0030-drops-145875},
  doi =		{10.4230/LIPIcs.ESA.2021.6},
  annote =	{Keywords: graph isomorphism, automorphism groups, algorithm engineering, parallel algorithms}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.30
Isomorphism Test for Digraphs with Weighted Edges

Authors: Adolfo Piperno

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{piperno:LIPIcs.SEA.2018.30,
  author =	{Piperno, Adolfo},
  title =	{{Isomorphism Test for Digraphs with Weighted Edges}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.30},
  URN =		{urn:nbn:de:0030-drops-89659},
  doi =		{10.4230/LIPIcs.SEA.2018.30},
  annote =	{Keywords: Practical Graph Isomorphism, Weighted Directed Graphs, Partition Refinement}
}
  • Refine by Author
  • 1 Anders, Markus
  • 1 Piperno, Adolfo
  • 1 Schweitzer, Pascal

  • Refine by Classification
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Shared memory algorithms

  • Refine by Keyword
  • 1 Partition Refinement
  • 1 Practical Graph Isomorphism
  • 1 Weighted Directed Graphs
  • 1 algorithm engineering
  • 1 automorphism groups
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2021

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