Dominators, directed bipolar orders, and independent spanning trees

Loukas Georgiadis, Robert E. Tarjan

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

12 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Pages375-386
Number of pages12
EditionPART 1
DOIs
StatePublished - Dec 1 2012
Event39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom
Duration: Jul 9 2012Jul 13 2012

Publication series

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

Other

Other39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
CountryUnited Kingdom
CityWarwick
Period7/9/127/13/12

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Dominators, directed bipolar orders, and independent spanning trees'. Together they form a unique fingerprint.

  • Cite this

    Georgiadis, L., & Tarjan, R. E. (2012). Dominators, directed bipolar orders, and independent spanning trees. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings (PART 1 ed., pp. 375-386). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7391 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-31594-7_32