TY - GEN
T1 - Dominator certification and independent spanning trees
T2 - 12th International Symposium on Experimental Algorithms, SEA 2013
AU - Georgiadis, Loukas
AU - Laura, Luigi
AU - Parotsidis, Nikos
AU - Tarjan, Robert E.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84884406862&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84884406862&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38527-8_26
DO - 10.1007/978-3-642-38527-8_26
M3 - Conference contribution
AN - SCOPUS:84884406862
SN - 9783642385261
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 284
EP - 295
BT - Experimental Algorithms - 12th International Symposium, SEA 2013, Proceedings
Y2 - 5 June 2013 through 7 June 2013
ER -