2017/10/12 by Henning Köehler, Henning Koehler, Koehler, Henning
Computer Science · Engineering · Mathematics · #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #acm:05C85 #cs.DM #graph theory and CDMA systems #math.CO #msc:05C85
paper · pdf · doi:10.48550/arxiv.1710.04333
12 pages, submitted to Discrete Mathematics and Theoretical Computer Science
arxiv created 2017/10/12 · openalex publication_date 2017/10/12 · arxiv updated 2017/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The modular decomposition of a graph is a canonical representation of its modules. Algorithms for computing the modular decomposition of directed and undirected graphs differ significantly, with the undirected case being simpler, and algorithms for directed graphs often work by reducing the problem to decomposing undirected graphs. In this paper we show that transitive acyclic digraphs have the same strong modules as their undirected versions. This simplifies reduction for transitive digraphs, requiring only the computation of strongly connected components. Furthermore, we are interested in permutation graphs, where both the graph and its complement are transitively orientable. Such graphs may be represented indirectly, as the transitive closure of a given graph. For non-transitive graphs we present a linear-time algorithm which allows us to identify prime-free modules w.r.t their transitive closure, which speeds up both modular decomposition and transitive orientation for sparse graphs. Finally, we show that any transitive orientation of a digraph's complement also transitively orients the complement of the digraph's transitive closure, allowing us to find such orientations in (near-)linear time.