TY - GEN
T1 - Maximum upward planar subgraph of a single-source embedded digraph
AU - Rextin, Aimal
AU - Healy, Patrick
PY - 2010
Y1 - 2010
N2 - We show how to compute a maximum upward planar single-source subgraph of a single-source embedded DAG G φ . We first show that finding a maximum upward planar subgraph of a single-source embedded digraph is NP-complete. We then give a new characterization of upward planar single-source digraphs. We use this characterization to present an algorithm that computes a maximum upward planar single-source subgraph of a single-source embedded DAG. This algorithm takes O(n 4) time in the worst case and O(n 3) time on average.
AB - We show how to compute a maximum upward planar single-source subgraph of a single-source embedded DAG G φ . We first show that finding a maximum upward planar subgraph of a single-source embedded digraph is NP-complete. We then give a new characterization of upward planar single-source digraphs. We use this characterization to present an algorithm that computes a maximum upward planar single-source subgraph of a single-source embedded DAG. This algorithm takes O(n 4) time in the worst case and O(n 3) time on average.
UR - http://www.scopus.com/inward/record.url?scp=77955044713&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-14031-0_14
DO - 10.1007/978-3-642-14031-0_14
M3 - Conference contribution
AN - SCOPUS:77955044713
SN - 3642140300
SN - 9783642140303
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 110
EP - 119
BT - Computing and Combinatorics - 16th Annual International Conference, COCOON 2010, Proceedings
T2 - 16th Annual International Computing and Combinatorics Conference, COCOON 2010
Y2 - 19 July 2010 through 21 July 2010
ER -