Loop nesting forests, dominators, and applications

Loukas Georgiadis, Luigi Laura, Nikos Parotsidis, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Loop nesting forests and dominator trees are important tools in program optimization and code generation, and they have applications in other diverse areas. In this work we first present carefully engineered implementations of efficient algorithms for computing a loop nesting forest of a given directed graph, including a very efficient algorithm that computes the forest in a single depth-first search. Then we revisit the problem of computing dominators and present efficient implementations of the algorithms recently proposed by Fraczak et al. [12], which include an algorithm for acyclic graphs and an algorithm that computes both the dominator tree and a loop nesting forest. We also propose a new algorithm than combines the algorithm of Fraczak et al. for acyclic graphs with the algorithm of Lengauer and Tarjan. Finally, we provide fast algorithms for the following related problems: computing bridges and testing 2-edge connectivity, verifying dominators and testing 2-vertex connectivity, and computing a low-high order and two independent spanning trees. We exhibit the efficiency of our algorithms experimentally on large graphs taken from a variety of application areas.

Original languageEnglish (US)
Title of host publicationExperimental Algorithms - 13th International Symposium, SEA 2014, Proceedings
PublisherSpringer Verlag
Pages174-186
Number of pages13
ISBN (Print)9783319079585
DOIs
StatePublished - Jan 1 2014
Event13th International Symposium on Experimental Algorithms, SEA 2014 - Copenhagen, Denmark
Duration: Jun 29 2014Jul 1 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8504 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Symposium on Experimental Algorithms, SEA 2014
CountryDenmark
CityCopenhagen
Period6/29/147/1/14

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Loop nesting forests, dominators, and applications'. Together they form a unique fingerprint.

Cite this