Dominators, directed bipolar orders, and independent spanning trees

DOI10.1007/978-3-642-31594-7_32MaRDI QIDQ2843263zbMATH OpenOpenAlexFDO

Authors Loukas Georgiadis, Robert E. Tarjan

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31594-7_32

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Dominator tree verification and vertex-disjoint paths
• Dominator tree certification and divergent spanning trees
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Finding dominators via disjoint set union
• Finding Dominators in Practice

Cited in

(6)

• Finding dominators via disjoint set union
• Strong articulation points and strong bridges in large scale graphs
• Computing the 2-blocks of directed graphs
• Dominator tree certification and divergent spanning trees
• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• Dominator tree verification and vertex-disjoint paths

This page was built for publication: Dominators, directed bipolar orders, and independent spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843263)