
doi: 10.46298/dmtcs.274
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 Ω (n^2). The best known time bounds for the problems are O(n+m) but they involve sophisticated techniques.
Substitution Decomposition, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Modular Decomposition, substitution decomposition, Graph theory (including graph drawing) in computer science, QA1-939, modular decomposition, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Transitive Orientation, transitive orientation, Mathematics
Substitution Decomposition, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Modular Decomposition, substitution decomposition, Graph theory (including graph drawing) in computer science, QA1-939, modular decomposition, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Transitive Orientation, transitive orientation, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
