@inproceedings{c310b0a56f834e55bc00009c0345d8b8,
title = "Parallel complexity of lexicographically first problems for tree-structured graphs",
abstract = "We study several P-complete graph problems and show that they are in NC if the input graphs are restricted to be tree-structured. These graphs are also known as partial k-trees, decomposable graphs or graphs of bounded tree width, and include outerplanar graphs, series-parallel graphs and Halin graphs. The particular problems investigated herein include the lexicographically first (l.f.) depth-first search tree and the l.f. maximal independent set. It is also shown that if a tree of faces of an outerplanar graph is given, then its dfs tree can be found in O(log2n) time using O(n/log2n) processors.",
author = "Bogdan Chlebus and Krzysztof Diks and Wojciech Rytter and Tomasz Szymacha",
year = "1989",
month = jan,
day = "1",
doi = "10.1007/3-540-51486-4_66",
language = "English (US)",
isbn = "9783540514862",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "185--195",
editor = "Antoni Kreczmar and Grazyna Mirkowska",
booktitle = "Mathematical Foundations of Computer Science 1989, Proceedings",
note = "14th Symposium on Mathematical Foundations of Computer Science, MFCS 1989 ; Conference date: 28-08-1989 Through 01-09-1989",
}