Dominator certification and independent spanning trees: An experimental study

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

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

9 Scopus citations

Abstract

We present the first implementations of certified algorithms for computing dominators, and exhibit their efficiency experimentally on graphs taken from a variety of applications areas. The certified algorithms are obtained by augmenting dominator-finding algorithms to compute a certificate of correctness that is easy to verify. A suitable certificate for dominators is obtained from the concepts of low-high orders and independent spanning trees. Therefore, our implementations provide efficient constructions of these concepts as well, which are interesting in their own right. Furthermore, we present an experimental study of efficient algorithms for computing dominators on large graphs.

Original languageEnglish (US)
Title of host publicationExperimental Algorithms - 12th International Symposium, SEA 2013, Proceedings
Pages284-295
Number of pages12
DOIs
StatePublished - 2013
Event12th International Symposium on Experimental Algorithms, SEA 2013 - Rome, Italy
Duration: Jun 5 2013Jun 7 2013

Publication series

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

Other

Other12th International Symposium on Experimental Algorithms, SEA 2013
Country/TerritoryItaly
CityRome
Period6/5/136/7/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Dominator certification and independent spanning trees: An experimental study'. Together they form a unique fingerprint.

Cite this