Dominators, directed bipolar orders, and independent spanning trees

Loukas Georgiadis; Robert E. Tarjan

doi:10.1007/978-3-642-31594-7_32

Dominators, directed bipolar orders, and independent spanning trees

Loukas Georgiadis, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

13 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 language	English (US)
Title of host publication	Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Pages	375-386
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-31594-7_32
State	Published - Dec 1 2012
Event	39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom Duration: Jul 9 2012 → Jul 13 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	7391 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/Territory	United Kingdom
City	Warwick
Period	7/9/12 → 7/13/12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-31594-7_32

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

Georgiadis, Loukas ; Tarjan, Robert E. / Dominators, directed bipolar orders, and independent spanning trees. Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1. ed. 2012. pp. 375-386 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{03c8362b98bc428f96ecc9b6a3a13961,

title = "Dominators, directed bipolar orders, and independent spanning trees",

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.",

author = "Loukas Georgiadis and Tarjan, {Robert E.}",

year = "2012",

month = dec,

day = "1",

doi = "10.1007/978-3-642-31594-7_32",

language = "English (US)",

isbn = "9783642315930",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "375--386",

booktitle = "Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings",

edition = "PART 1",

note = "39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 ; Conference date: 09-07-2012 Through 13-07-2012",

}

Georgiadis, L & Tarjan, RE 2012, Dominators, directed bipolar orders, and independent spanning trees. in Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 7391 LNCS, pp. 375-386, 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012, Warwick, United Kingdom, 7/9/12. https://doi.org/10.1007/978-3-642-31594-7_32

Dominators, directed bipolar orders, and independent spanning trees. / Georgiadis, Loukas; Tarjan, Robert E.
Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1. ed. 2012. p. 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).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

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

Dominators, directed bipolar orders, and independent spanning trees

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this