Modular decomposition and transitive orientation Export

@article{citeulike:2097464, abstract = {A module of an undirected graph is a set X of nodes such for each node x not in X, either every member of X is adjacent to x, or no member of X is adjacent to x. There is a canonical linear-space representation for the modules of a graph, called the modular decomposition. Closely related to modular decomposition is the transitive orientation problem, which is the problem of assigning a direction to each edge of a graph so that the resulting digraph is transitive. A graph is a comparability graph if such an assignment is possible. We give O(n + m) algorithms for modular decomposition and transitive orientation, where n and m are the number of vertices and edges of the graph. This gives linear time bounds for recognizing permutation graphs, maximum clique and minimum vertex coloring on comparability graphs, and other combinatorial problems on comparability graphs and their complements.}, author = {Mcconnell, Ross M. and Spinrad, Jeremy P.}, citeulike-article-id = {2097464}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0012-365X(98)00319-7}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0012-365X(98)00319-7}, citeulike-linkout-2 = {http://www.sciencedirect.com/science/article/B6V00-42NRV3G-F/2/598bde099cb44ed913254d1123b58a7d}, day = {28}, doi = {10.1016/S0012-365X(98)00319-7}, journal = {Discrete Mathematics}, keywords = {graph, modular}, month = {April}, number = {1-3}, pages = {189--241}, posted-at = {2008-11-30 07:20:06}, priority = {2}, title = {Modular decomposition and transitive orientation}, url = {http://dx.doi.org/10.1016/S0012-365X(98)00319-7}, volume = {201}, year = {1999} }

TY - JOUR ID - citeulike:2097464 L3 - citeulike-article-id:2097464 N2 - A module of an undirected graph is a set X of nodes such for each node x not in X, either every member of X is adjacent to x, or no member of X is adjacent to x. There is a canonical linear-space representation for the modules of a graph, called the modular decomposition. Closely related to modular decomposition is the transitive orientation problem, which is the problem of assigning a direction to each edge of a graph so that the resulting digraph is transitive. A graph is a comparability graph if such an assignment is possible. We give O(n + m) algorithms for modular decomposition and transitive orientation, where n and m are the number of vertices and edges of the graph. This gives linear time bounds for recognizing permutation graphs, maximum clique and minimum vertex coloring on comparability graphs, and other combinatorial problems on comparability graphs and their complements. IS - 1-3 JF - Discrete Mathematics EP - 241 TI - Modular decomposition and transitive orientation VL - 201 SP - 189 KW - graph KW - modular AU - Mcconnell, Ross AU - Spinrad, Jeremy PY - 1999/04/28/ UR - http://dx.doi.org/10.1016/S0012-365X(98)00319-7 ER -