Ordered Vertex Partitioning

@article{citeulike:2133014, abstract = {A transitive orientation of a graph is an orientation of the edges that produces a transitive digraph. The modular decomposition of a graph is a canonical representation of all of its modules. Finding a transitive orientation and finding the modular decomposition are in some sense dual problems. In this paper, we describe a simple O(n + m log n) algorithm that uses this duality to find both a transitive orientation and the modular decomposition. Though the running time is not optimal, this algorithm is much simpler than any previous algorithms that are not Ω(n2). The best known time bounds for the problems are O(n+m) but they involve sophisticated techniques.}, author = {Mcconnell, Ross M. and Spinrad, Jeremy P. }, citeulike-article-id = {2133014}, journal = {Discrete Mathematics \& Theoretical Computer Science}, keywords = {algorithms, graph}, number = {1}, pages = {45--60}, posted-at = {2007-12-16 17:59:06}, priority = {2}, publisher = {Laboratoire Lorrain de Recherche en Informatique et ses Applications, LORIA}, title = {Ordered Vertex Partitioning}, url = {http://www.emis.de/journals/DMTCS/volumes/abstracts/dm040104.abs.html}, volume = {4}, year = {2000} }

TY - JOUR ID - citeulike:2133014 L3 - citeulike-article-id:2133014 TI - Ordered Vertex Partitioning JF - Discrete Mathematics & Theoretical Computer Science VL - 4 IS - 1 SP - 45 EP - 60 PB - Laboratoire Lorrain de Recherche en Informatique et ses Applications, LORIA N2 - A transitive orientation of a graph is an orientation of the edges that produces a transitive digraph. The modular decomposition of a graph is a canonical representation of all of its modules. Finding a transitive orientation and finding the modular decomposition are in some sense dual problems. In this paper, we describe a simple O(n + m log n) algorithm that uses this duality to find both a transitive orientation and the modular decomposition. Though the running time is not optimal, this algorithm is much simpler than any previous algorithms that are not Ω(n2). The best known time bounds for the problems are O(n+m) but they involve sophisticated techniques. KW - algorithms KW - graph AU - Mcconnell, Ross AU - Spinrad, Jeremy PY - 2000/// UR - http://www.emis.de/journals/DMTCS/volumes/abstracts/dm040104.abs.html ER -