Skip to main content

Marc Hellmuth: Explicit Modular Decomposition

Time: Wed 2022-11-02 13.30

Location: Albano, Cramer room

Participating: Marc Hellmuth (SU)

Export to calendar


The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a rooted labeled tree (T,t) whose vertices are labeled as "series" (1), "parallel" (0) or "prime". However, full information of G is provided by its modular decomposition tree (T,t) only, if G does not contain prime modules. In this case, (T,t) explains G, i.e., {x,y} is an edge in G if and only if the lowest common ancestor lca_T(x,y) of x and y has label "1". This information, however, gets lost whenever (T,t) contains vertices with label "prime".

Explicit Modular Decomposition is a rather novel concept and aims at replacing "prime" vertices in the modular decomposition tree by suitable 0/1-labeled substructure to obtain 0/1-labeled networks to explain a given graph. We characterize here the class of graphs that can be explained by 0/1-labeled median graphs as well as 0/1-labeled galled trees.