Copyright Notice:

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

L. Gianinazzi, T. Hoefler:

 Parallel Planar Subgraph Isomorphism and Vertex Connectivity

(In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'20), presented in , ACM, ISBN: , Jul. 2020, )
Best Paper Finalist (5/68)

Abstract

We present the first parallel fixed-parameter algorithm for subgraph isomorphism in planar graphs, bounded-genus graphs, and more generally all minor-closed graphs of locally bounded treewidth. Our randomized low depth algorithm has a near-linear work dependency on the size of the target graph. Existing low depth algorithms do not guarantee that the work remains asymptotically the same for any constant-sized pattern. By using a connection to certain separating cycles, our subgraph isomorphism algorithm can decide the vertex connectivity of a planar graph (with high probability) in asymptotically near-linear work and poly-logarithmic depth. Previously, no sub-quadratic work and poly-logarithmic depth bound was known in planar graphs (in particular for distinguishing between four-connected and five-connected graphs).

Documents

download article:
download slides:


Recorded talk (best effort)

 

BibTeX

@inproceedings{gianinazzi-par-sg-isomorphism,
  author={Lukas Gianinazzi and Torsten Hoefler},
  title={{Parallel Planar Subgraph Isomorphism and Vertex Connectivity}},
  year={2020},
  month={7},
  booktitle={Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'20)},
  location={},
  publisher={ACM},
  isbn={},
  note={},
  doi={10.1145/3350755.3400259},
}