TY - GEN
T1 - Dominators, directed bipolar orders, and independent spanning trees
AU - Georgiadis, Loukas
AU - Tarjan, Robert E.
PY - 2012/12/1
Y1 - 2012/12/1
N2 - We consider problems related to dominators and independent spanning trees in flowgraphs and provide linear-time algorithms for their solutions. We introduce the notion of a directed bipolar order, generalizing a previous notion of Plein and Cheriyan and Reif. We show how to construct such an order from information computed by several known algorithms for finding dominators. We show how to concurrently verify the correctness of a dominator tree D and a directed bipolar order O very simply, and how to construct from D and O two spanning trees whose paths are disjoint except for common dominators. Finally, we describe alternative ways to verify dominators without using a directed bipolar order.
AB - We consider problems related to dominators and independent spanning trees in flowgraphs and provide linear-time algorithms for their solutions. We introduce the notion of a directed bipolar order, generalizing a previous notion of Plein and Cheriyan and Reif. We show how to construct such an order from information computed by several known algorithms for finding dominators. We show how to concurrently verify the correctness of a dominator tree D and a directed bipolar order O very simply, and how to construct from D and O two spanning trees whose paths are disjoint except for common dominators. Finally, we describe alternative ways to verify dominators without using a directed bipolar order.
UR - http://www.scopus.com/inward/record.url?scp=84883815233&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883815233&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31594-7_32
DO - 10.1007/978-3-642-31594-7_32
M3 - Conference contribution
AN - SCOPUS:84883815233
SN - 9783642315930
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 375
EP - 386
BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Y2 - 9 July 2012 through 13 July 2012
ER -