A survey on algorithmic aspects of modular decomposition
---
paper_title: Graph Classes: A Survey

paper_content:

Preface 1. Basic Concepts 2. Perfection, Generalized Perfection, and Related Concepts 3. Cycles, Chords and Bridges 4. Models and Interactions 5. Vertex and Edge Orderings 6. Posets 7. Forbidden Subgraphs 8. Hypergraphs and Graphs 9. Matrices and Polyhedra 10. Distance Properties 11. Algebraic Compositions and Recursive Definitions 12. Decompositions and Cutsets 13. Threshold Graphs and Related Concepts 14. The Strong Perfect Graph Conjecture Appendix A. Recognition Appendix B. Containment Relationships Bibliography Index.
---
paper_title: A characterization of perfect graphs

paper_content:

Throughout this note, graph means finite, undirected graph without loops and multiple edges.
---
paper_title: Three Partition Refinement Algorithms

paper_content:

We present improved partition refinement algorithms for three problems: lexicographic sorting, relational coarsest partition, and double lexical ordering. Our double lexical ordering algorithm uses a new, efficient method for unmerging two sorted sets.
---
paper_title: Ordered Vertex Partitioning

paper_content:

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.
---
paper_title: Linear-time modular decomposition and efficient transitive orientation of comparability graphs

paper_content:

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. The modular decomposition facilitates solution of a number of combinatorial problems on certain classes of graphs, and algorithms for computing it have a lengthy history. 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, if such an assignment is possible. We give the lirst linear-time algorithm for modular decomposition, and a new bound of 0 (ri +m logn) on transitive orientation and the problem of recognizing permutation graphs and two-dimensional partial orders.
---
paper_title: Computing common intervals of K permutations, with applications to modular decomposition of graphs

paper_content:

We introduce a new way to compute common intervals of K permutations based on a very simple and general notion of generators of common intervals. This formalism leads to simple and efficient algorithms to compute the set of all common intervals of K permutations, that can contain a quadratic number of intervals, as well as a linear space basis of this set of common intervals. Finally, we show how our results on permutations can be used for computing the modular decomposition of graphs in linear time.
---
paper_title: Modular decomposition and transitive orientation

paper_content:

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. c 1999 Published by Elsevier Science B.V. All rights reserved
---
paper_title: Substitution decomposition for discrete structures and connections with combinatorial optimization

paper_content:

In this paper we deal with the substitution decomposition as known for Boolean functions, set systems and relations. It is shown how combinatorial optimization problems, particularly on graphs, partial orders, project networks, (in-) dependence systems and clutters, naturally lead, under weak assumptions, to this kind of decomposition via certain uniqueness results. We then generalize the common features of this type of decomposition from the special cases to a quite general algebraic level, covering infinite cases, and deduce a general Jordan-Holder theorem as well as uniqeness results for the associated composition tree in this general setting. These results are then reinterpreted for the special cases, and the computational aspects of the substitution decomposition are discussed. Throughout, applications to many problems concerning discrete structures are included, as are connections with other approaches in these fields, in particular the split decomposition.
---
paper_title: Algorithmic graph theory and perfect graphs

paper_content:

Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails. The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition. New edition of the "Classic" book on the topic Wonderful introduction to a rich research area Leading author in the field of algorithmic graph theory Beautifully written for the new mathematician or computer scientist Comprehensive treatment
---
paper_title: Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions

paper_content:

In the last years, decomposition techniques have seen an increasing application to the solution of problems from operations research and combinatorial optimization, in particular in network theory and graph theory. This paper gives a broad treatment of a particular aspect of this approach, viz. the design of algorithms to compute the decomposition possibilities for a large class of discrete structures. The decomposition considered is thesubstitution decomposition (also known as modular decomposition, disjunctive decomposition, X-join or ordinal sum). Under rather general assumptions on the type of structure considered, these (possibly exponentially many) decomposition possibilities can be appropriately represented in acomposition tree of polynomial size. The task of determining this tree is shown to be polynomially equivalent to the seemingly weaker task of determining the closed hull of a given set w.r.t. a closure operation associated with the substitution decomposition. Based on this reduction, we show that for arbitrary relations the composition tree can be constructed in polynomial time. For clutters and monotonic Boolean functions, this task of constructing the closed hull is shown to be Turing-reducible to the problem of determining the circuits of the independence system associated with the clutter or the prime implicants of the Boolean function. This leads to polynomial algorithms for special clutters or monotonic Boolean functions. However, these results seem not to be extendable to the general case, as we derive exponential lower bounds for oracle decomposition algorithms for arbitrary set systems and Boolean functions.
---
paper_title: An O ( n 2 ) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs

paper_content:

Abstract This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in O ( n 2 ) time, when n is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, and the restriction of the decomposition to graphs is known as the modular decomposition or substitution decomposition . The decomposition has applications in solving certain scheduling problems and a number of problems on graphs and partial orders. Two algorithms with a comparable time bound have previously been published for undirected graphs, but they make use of elaborate data structures that limit their practical use, and they have no easy generalization to directed graphs or two-structures.
---
paper_title: Graph decompositions and factorizing permutations

paper_content:

A factorizing permutation of a given graph is simply a permutation of the vertices in which all decomposition sets appear to be factors. Such a concept seems to play a central role in recent papers dealing with graph decomposition. It is applied here for modular decomposition and we propose a linear algorithm that computes the whole decomposition tree when a factorizing permutation is provided. This algorithm can be seen as a common generalization of Ma and Hsu for modular decomposition of chordal graphs and Habib, Huchard and Spinrad for inheritance graphs decomposition. It also suggests many new decomposition algorithms for various notions of graph decompositions.
---
paper_title: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations

paper_content:

Modular decomposition is fundamental for many important problems in algorithmic graph theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been a drive towards a practical, linear-time algorithm for the problem. This paper posits such an algorithm; we present a linear-time modular decomposition algorithm that proceeds in four straightforward steps. This is achieved by introducing the notion of factorizing permutations to an earlier recursive approach. The only data structure used is an ordered list of trees, and each of the four steps amounts to simple traversals of these trees. Previous algorithms were either exceedingly complicated or resorted to impractical data-structures.
---
paper_title: Graphs with unique maximal clumpings

paper_content:

A partition of the vertices of a graph is called a clumping if, for vertices in distinct partition classes, adjacency depends only on the partition classes, not on the specific vertices. We give a simple necessary and sufficient condition for a finite graph to have a unique maximal clumping. We also investigate the extent to which this and related results generalize to infinite graphs.
---
paper_title: Fast Algorithms to Enumerate All Common Intervals of Two Permutations

paper_content:

Given two permutations of n elements, a pair of intervals of these permutations consisting of the same set of elements is called a commoninterval . Some genetic algorithms based on such common intervals have been proposed for sequencing problems and have exhibited good prospects. In this paper we propose three types of fast algorithms to enumerate all common intervals: (i) a simple O(n 2 ) time algorithm (LHP), whose expected running time becomes O(n) for two randomly generated permutations, (ii) a practically fast O(n 2 ) time algorithm (MNG) using the reverse Monge property, and (iii) an O(n+K) time algorithm (RC), where K\((\leq {n \choose 2})\) is the number of common intervals. It will also be shown that the expected number of common intervals for two random permutations is O(1) . This result gives a reason for the phenomenon that the expected time complexity O(n) of the algorithm LHP is independent of K . Among the proposed algorithms, RC is most desirable from the theoretical point of view; however, it is quite complicated compared with LHP and MNG. Therefore, it is possible that RC is slower than the other two algorithms in some cases. For this reason, computational experiments for various types of problems with up to n=10 6 are conducted. The results indicate that (i) LHP and MNG are much faster than RC for two randomly generated permutations, and (ii) MNG is rather slower than LHP for random inputs; however, there are cases in which LHP requires Ω(n 2 ) time, but MNG runs in o(n 2 ) time and is faster than both LHP and RC.
---
paper_title: Tree-Representation of Set Families in Graph Decompositions and Efficient Algorithms

paper_content:

We address some issues around three main topics: on the representation of set families by a tree, on decompositions of graphs, and on algorithms on graphs. Our study ranges from theoretical questions in combinatorics to the design of algorithms in computational biology, and also includes several decomposition schemes of graphs, as well as some issues in combinatorial optimization. The first half of the thesis has two foci. Firstly, in order to estimate the number of set families satisfying some closure axioms, we have developed new tools and techniques to find tree-like representations for them. Then, we have given some applications of the previous results in a branch of graph theory called graph decomposition. The second half of the thesis is devoted to algorithmic applications of set representations and decompositions to three graph problems. For each of them we show how the philosophy of decomposition can help to provide efficient solutions. We also show how to apply our three solutions to solve three other graph problems.
---
paper_title: A min-max relation for submodular functions on graphs

paper_content:

Publisher Summary This chapter describes a min-max relation for submodular functions on graphs. It proves a new combinatorial min-max equality that unifies and extends results including the matroid intersection theorem and the theorem of Lucchesi and Younger on the minimum number of edges, which meet every directed cut in a graph. The method of proof used in the chapter generalizes the method used to prove the polymatroid intersection theorem and the method used to prove the Lucchesi-Younger Theorem including an idea that Lovasz attributes to Neil Robertson.
---
paper_title: Tree-Representation of Set Families in Graph Decompositions and Efficient Algorithms

paper_content:

We address some issues around three main topics: on the representation of set families by a tree, on decompositions of graphs, and on algorithms on graphs. Our study ranges from theoretical questions in combinatorics to the design of algorithms in computational biology, and also includes several decomposition schemes of graphs, as well as some issues in combinatorial optimization. The first half of the thesis has two foci. Firstly, in order to estimate the number of set families satisfying some closure axioms, we have developed new tools and techniques to find tree-like representations for them. Then, we have given some applications of the previous results in a branch of graph theory called graph decomposition. The second half of the thesis is devoted to algorithmic applications of set representations and decompositions to three graph problems. For each of them we show how the philosophy of decomposition can help to provide efficient solutions. We also show how to apply our three solutions to solve three other graph problems.
---
paper_title: Graph decompositions and factorizing permutations

paper_content:

A factorizing permutation of a given graph is simply a permutation of the vertices in which all decomposition sets appear to be factors. Such a concept seems to play a central role in recent papers dealing with graph decomposition. It is applied here for modular decomposition and we propose a linear algorithm that computes the whole decomposition tree when a factorizing permutation is provided. This algorithm can be seen as a common generalization of Ma and Hsu for modular decomposition of chordal graphs and Habib, Huchard and Spinrad for inheritance graphs decomposition. It also suggests many new decomposition algorithms for various notions of graph decompositions.
---
paper_title: Graph Classes: A Survey

paper_content:

Preface 1. Basic Concepts 2. Perfection, Generalized Perfection, and Related Concepts 3. Cycles, Chords and Bridges 4. Models and Interactions 5. Vertex and Edge Orderings 6. Posets 7. Forbidden Subgraphs 8. Hypergraphs and Graphs 9. Matrices and Polyhedra 10. Distance Properties 11. Algebraic Compositions and Recursive Definitions 12. Decompositions and Cutsets 13. Threshold Graphs and Related Concepts 14. The Strong Perfect Graph Conjecture Appendix A. Recognition Appendix B. Containment Relationships Bibliography Index.
---
paper_title: Algorithmic Aspects of a General Modular Decomposition Theory

paper_content:

A new general decomposition theory inspired from modular graph decomposition is presented. This helps unifying modular decomposition on different structures, including (but not restricted to) graphs. Moreover, even in the case of graphs, the terminology ``module'' not only captures the classical graph modules but also allows to handle 2-connected components, star-cutsets, and other vertex subsets. The main result is that most of the nice algorithmic tools developed for modular decomposition of graphs still apply efficiently on our generalisation of modules. Besides, when an essential axiom is satisfied, almost all the important properties can be retrieved. For this case, an algorithm given by Ehrenfeucht, Gabow, McConnell and Sullivan 1994 is generalised and yields a very efficient solution to the associated decomposition problem.
---
paper_title: Graph Classes: A Survey

paper_content:

Preface 1. Basic Concepts 2. Perfection, Generalized Perfection, and Related Concepts 3. Cycles, Chords and Bridges 4. Models and Interactions 5. Vertex and Edge Orderings 6. Posets 7. Forbidden Subgraphs 8. Hypergraphs and Graphs 9. Matrices and Polyhedra 10. Distance Properties 11. Algebraic Compositions and Recursive Definitions 12. Decompositions and Cutsets 13. Threshold Graphs and Related Concepts 14. The Strong Perfect Graph Conjecture Appendix A. Recognition Appendix B. Containment Relationships Bibliography Index.
---
paper_title: Recognizing P 4 -sparse graphs in linear time

paper_content:

A graph G is $P_4 $-sparse if no set of five vertices in G induces more than one chordless path of length three. $P_4 $-sparse graphs generalize both the class of cographs and the class of $P_4 $-reducible graphs. One remarkable feature of $P_4 $-sparse graphs is that they admit a tree representation unique up to isomorphism. It has been shown that this tree representation can be obtained in polynomial time. This paper gives a linear time algorithm to recognize $P_4 $-sparse graphs and shows how the data structures returned by the recognition algorithm can be used to construct the corresponding tree representation in linear time.
---
paper_title: P-Components and the Homogeneous Decomposition of Graphs

paper_content:

In this paper we introduce and investigate the notion of p-connectedness. As it turns out, this concept leads naturally to a unique tree representation for arbitrary graphs: the leaves of this tree are the p-connected components along with weak vertices, that is, vertices of the graph that belong to no p-connected component. We then show how to refine this decomposition to obtain a new decomposition that extends the well-known modular decomposition.
---
paper_title: Primitivity is hereditary for 2-structures

paper_content:

Abstract It is proved that each primitive 2-structure on n elements ( n ⩾3) contains a primitive substructure on either ( n −1) or ( n −2) elements.
---
paper_title: Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures

paper_content:

Abstract A finite, indecomposable partially ordered set is said to be critically indecomposable if, whenever an element is removed, the resulting induced partially ordered set is not indecomposable. The same terminology can be applied to graphs, tournaments, or any other relational structure whose relations are binary and irreflexive. It will be shown in this paper that critically indecomposable partially ordered sets are rather scarce; indeed, there are none of odd order, there is exactly one of order 4, and for each even k ⪖ 6 there are exactly two of order k . The same applies to graphs. For tournaments, there are none have even order, there is exactly one of order 3, and for each odd k ⪖ 5 there are precisely three of order k . In general, for arbitrary irreflexive binary relational structures, we will see that all critical indecomposables fall into one of nine infinite classes. Four of these classes are even—they contain no structures of odd order and for even k ⪖ 6 they each contain (up to a certain type of equivalence) exactly one structure of order k . The five other classes sre odd—they contain no structures of even order and for each odd k ⪖ 5 they each contain exactly one structure of order k . From this characterization of critically indecomposable structures, it will be evident that all indecomposable substructures of critically indecomposable structures are themselves critically indecomposable. Finally, it is proved that every indecomposable structure of order n + 2 ( n ⪖ 5) has an indecomposable substructure of order n .
---
paper_title: A simple linear time LexBFS cograph recognition algorithm

paper_content:

This paper introduces a new simple linear time algorithm to recognize cographs (graphs without an induced P 4 ). Unlike other cograph recognition algorithms, the new algorithm uses a multisweep Lexicographic Breadth First Search (LexBFS) approach, and introduces a new variant of LexBFS, called LexBFS-, operating on the complement of the given graph G and breaking ties with respect to an initial LexBFS. The algorithm either produces the cotree of G or identifies an induced P4).
---
paper_title: Dynamic Distance Hereditary Graphs Using Split Decomposition∗

paper_content:

The problem of maintaining a representation of a dynamic graph as long as a certain property is satisfied has recently been considered for a number of properties. This paper presents an optimal algorithm for this problem on vertex-dynamic connected distance hereditary graphs: both vertex insertion and deletion have complexity O(d), where d is the degree of the vertex involved in the modification. Our vertex-dynamic algorithm is competitive with the existing linear time recognition algorithms of distance hereditary graphs, and is also simpler. Besides, we get a constant time edge-dynamic recognition algorithm. To achieve this, we revisit the split decomposition by introducing graph-labelled trees. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem.
---
paper_title: A simple linear time algorithm for cograph recognition

paper_content:

In this paper, we describe a new simple linear time algorithm to recognize cographs. Cographs are exactly the P"4-free graphs (where P"4 denotes the path with 4 vertices). The recognition process works in two steps. First, we use partition refinement techniques to produce a factorizing permutation, i.e., an ordering of the vertices in which the strong modules appear consecutively. Then a very simple test algorithm is provided to check whether the given graph is a cograph, using a single sweep of the permutation obtained in the first step.
---
paper_title: Longest Common Separable Pattern Among Permutations

paper_content:

In this paper, we study the problem of finding the longest common separable pattern among several permutations. We first give a polynomial-time algorithm when the number of input permutations is fixed and next show that the problem is NP-hard for an arbitrary number of input permutations even if these permutations are separable. ::: ::: On the other hand, we show that the NP-hard problem of finding the longest common pattern between two permutations cannot be approximated better than within a ratio of √opt (where opt is the size of an optimal solution) when taking common patterns belonging to patternavoiding permutation classes.
---
paper_title: Graphs indecomposable with respect to the X-join

paper_content:

In his paper [3], Sabidussi defined the X-join of a family of graphs. This concept has also appeared in the work of Foulis and Randall on empirical logic [1,2]. In this paper, we investigate those graphs which do not have a nontrivial representation as the X-join of some family of graphs.
---
paper_title: Graph Classes: A Survey

paper_content:

Preface 1. Basic Concepts 2. Perfection, Generalized Perfection, and Related Concepts 3. Cycles, Chords and Bridges 4. Models and Interactions 5. Vertex and Edge Orderings 6. Posets 7. Forbidden Subgraphs 8. Hypergraphs and Graphs 9. Matrices and Polyhedra 10. Distance Properties 11. Algebraic Compositions and Recursive Definitions 12. Decompositions and Cutsets 13. Threshold Graphs and Related Concepts 14. The Strong Perfect Graph Conjecture Appendix A. Recognition Appendix B. Containment Relationships Bibliography Index.
---
paper_title: Ordered Vertex Partitioning

paper_content:

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.
---
paper_title: A Simple Linear-Time Modular Decomposition Algorithm

paper_content:

The first polynomial time algorithm (O(n)) for modular decomposition appeared in 1972 [8] and since then there have been incremental improvements, eventually resulting in linear-time algorithms [22, 7, 23, 9]. Although having optimal time complexity these algorithms are quite complicated and difficult to implement. In this paper we present an easily implementable linear-time algorithm for modular decomposition. This algorithm uses the notion of factorizing permutation and a new data-structure, the Ordered Chain Partitions.
---
paper_title: Fully-dynamic recognition algorithm and certificate for directed cographs

paper_content:

This paper presents an optimal fully-dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in $\mathcal{O}(d)$ time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular tree decomposition is updated; otherwise, a certificate is returned within the same complexity.
---
paper_title: A simple linear time LexBFS cograph recognition algorithm

paper_content:

This paper introduces a new simple linear time algorithm to recognize cographs (graphs without an induced P 4 ). Unlike other cograph recognition algorithms, the new algorithm uses a multisweep Lexicographic Breadth First Search (LexBFS) approach, and introduces a new variant of LexBFS, called LexBFS-, operating on the complement of the given graph G and breaking ties with respect to an initial LexBFS. The algorithm either produces the cotree of G or identifies an induced P4).
---
paper_title: Dynamic Distance Hereditary Graphs Using Split Decomposition∗

paper_content:

The problem of maintaining a representation of a dynamic graph as long as a certain property is satisfied has recently been considered for a number of properties. This paper presents an optimal algorithm for this problem on vertex-dynamic connected distance hereditary graphs: both vertex insertion and deletion have complexity O(d), where d is the degree of the vertex involved in the modification. Our vertex-dynamic algorithm is competitive with the existing linear time recognition algorithms of distance hereditary graphs, and is also simpler. Besides, we get a constant time edge-dynamic recognition algorithm. To achieve this, we revisit the split decomposition by introducing graph-labelled trees. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem.
---
paper_title: Substitution decomposition for discrete structures and connections with combinatorial optimization

paper_content:

In this paper we deal with the substitution decomposition as known for Boolean functions, set systems and relations. It is shown how combinatorial optimization problems, particularly on graphs, partial orders, project networks, (in-) dependence systems and clutters, naturally lead, under weak assumptions, to this kind of decomposition via certain uniqueness results. We then generalize the common features of this type of decomposition from the special cases to a quite general algebraic level, covering infinite cases, and deduce a general Jordan-Holder theorem as well as uniqeness results for the associated composition tree in this general setting. These results are then reinterpreted for the special cases, and the computational aspects of the substitution decomposition are discussed. Throughout, applications to many problems concerning discrete structures are included, as are connections with other approaches in these fields, in particular the split decomposition.
---
paper_title: Algorithmic graph theory and perfect graphs

paper_content:

Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails. The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition. New edition of the "Classic" book on the topic Wonderful introduction to a rich research area Leading author in the field of algorithmic graph theory Beautifully written for the new mathematician or computer scientist Comprehensive treatment
---
paper_title: Algorithmic Aspects of Vertex Elimination on Graphs

paper_content:

We consider a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse symmetric positive definite systems of linear equations. We give a new linear-time algorithm to calculate the fill-in produced by any elimination ordering, and we give two new related algorithms for finding orderings with special properties. One algorithm, based on breadth-first search, finds a perfect elimination ordering, if any exists, in $O(n + e)$ time, if the problem graph has n vertices and e edges. An extension of this algorithm finds a minimal (but not necessarily minimum) ordering in $O(ne)$ time. We conjecture that the problem of finding a minimum ordering is NP-complete
---
paper_title: Decomposition of Directed Graphs

paper_content:

A composition for directed graphs which generalizes the substitution (or X-join) composition of graphs and digraphs, as well as the graph version of set-family composition, is described. It is proved that a general decomposition theory can be applied to the resulting digraph decomposition. A consequence is a theorem which asserts the uniqueness of a decomposition of any digraph, each member of the decomposition being either indecomposable or “special”. The special digraphs are completely characterized; they are members of a few interesting classes. Efficient decomposition algorithms are also presented.
---
paper_title: Incremental modular decomposition

paper_content:

Modular decomposition is a form of graph decomposition that has been discovered independently by researchers in graph theory, game theory, network theory, and other areas. This paper reduces the time needed to find the modular decomposition of a graph from O( n 3 ) to O( n 2 ). Together with a new algorithm for transitive orientation given in [21], this leads to fast new algorithms for a number of problems in graph recognition and isomorphism, including recognition of comparability graphs and permutation graphs. The new algorithm works by inserting each vertex successively into the decomposition tree, using O( n ) time to insert each vertex.
---
paper_title: A simple linear time algorithm for cograph recognition

paper_content:

In this paper, we describe a new simple linear time algorithm to recognize cographs. Cographs are exactly the P"4-free graphs (where P"4 denotes the path with 4 vertices). The recognition process works in two steps. First, we use partition refinement techniques to produce a factorizing permutation, i.e., an ordering of the vertices in which the strong modules appear consecutively. Then a very simple test algorithm is provided to check whether the given graph is a cograph, using a single sweep of the permutation obtained in the first step.
---
paper_title: A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs

paper_content:

We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time.
---
paper_title: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations

paper_content:

Modular decomposition is fundamental for many important problems in algorithmic graph theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been a drive towards a practical, linear-time algorithm for the problem. This paper posits such an algorithm; we present a linear-time modular decomposition algorithm that proceeds in four straightforward steps. This is achieved by introducing the notion of factorizing permutations to an earlier recursive approach. The only data structure used is an ordered list of trees, and each of the four steps amounts to simple traversals of these trees. Previous algorithms were either exceedingly complicated or resorted to impractical data-structures.
---
paper_title: Bimodular decomposition of bipartite graphs

paper_content:

This paper gives a decomposition theory for bipartite graphs. It uses bimodules, a special case of 2-modules (also known as homogeneous pairs, an extension of both modules and splits). It is shown how a unique decomposition tree represents the bimodular decomposition of a bipartite graph, with strong analogs with modular decomposition of graphs. An O(mn 3 ) algorithm for this decomposition is provided. At least a classification of the 2-modules of a bipartite graph is given.
---
paper_title: Tree-Representation of Set Families in Graph Decompositions and Efficient Algorithms

paper_content:

We address some issues around three main topics: on the representation of set families by a tree, on decompositions of graphs, and on algorithms on graphs. Our study ranges from theoretical questions in combinatorics to the design of algorithms in computational biology, and also includes several decomposition schemes of graphs, as well as some issues in combinatorial optimization. The first half of the thesis has two foci. Firstly, in order to estimate the number of set families satisfying some closure axioms, we have developed new tools and techniques to find tree-like representations for them. Then, we have given some applications of the previous results in a branch of graph theory called graph decomposition. The second half of the thesis is devoted to algorithmic applications of set representations and decompositions to three graph problems. For each of them we show how the philosophy of decomposition can help to provide efficient solutions. We also show how to apply our three solutions to solve three other graph problems.
---
paper_title: A fully dynamic algorithm for modular decomposition and recognition of cographs

paper_content:

The problem of dynamically recognizing a graph property calls for efficiently deciding if an input graph satisfies the property under repeated modifications to its set of vertices and edges. The input to the problem consists of a series of modifications to be performed on the graph. The objective is to maintain a representation of the graph as long as the property holds, and to detect when it ceases to hold. In this paper, we solve the dynamic recognition problem for the class of cographs and some of its subclasses. Our approach is based on maintaining the modular decomposition tree of the dynamic graph, and using this tree for the recognition. We give the first fully dynamic algorithm for maintaining the modular decomposition tree of a cograph. We thereby obtain fully dynamic algorithms for the recognition of cographs, threshold graphs, and trivially perfect graphs. All these algorithms work in constant time per edge modification and O(d) time per d-degree vertex modification.
---
paper_title: Three Partition Refinement Algorithms

paper_content:

We present improved partition refinement algorithms for three problems: lexicographic sorting, relational coarsest partition, and double lexical ordering. Our double lexical ordering algorithm uses a new, efficient method for unmerging two sorted sets.
---
paper_title: Minimal proper interval completions

paper_content:

Given an arbitrary graph G = (V,E) and a proper interval graph H = (V, F) with E C F we say that H is a proper interval completion of G. The graph H is called a minimal proper interval completion of G if, for any sandwich graph H' = (V, F') with E C F' ⊂ F, H' is not a proper interval graph. In this paper we give a O(n + m) time algorithm computing a minimal proper interval completion of an arbitrary graph. The output is a proper interval model of the completion.
---
paper_title: Ordered Vertex Partitioning

paper_content:

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.
---
paper_title: Ordered Vertex Partitioning

paper_content:

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.
---
paper_title: An O ( n 2 ) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs

paper_content:

Abstract This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in O ( n 2 ) time, when n is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, and the restriction of the decomposition to graphs is known as the modular decomposition or substitution decomposition . The decomposition has applications in solving certain scheduling problems and a number of problems on graphs and partial orders. Two algorithms with a comparable time bound have previously been published for undirected graphs, but they make use of elaborate data structures that limit their practical use, and they have no easy generalization to directed graphs or two-structures.
---
paper_title: An O ( n 2 ) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs

paper_content:

Abstract This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in O ( n 2 ) time, when n is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, and the restriction of the decomposition to graphs is known as the modular decomposition or substitution decomposition . The decomposition has applications in solving certain scheduling problems and a number of problems on graphs and partial orders. Two algorithms with a comparable time bound have previously been published for undirected graphs, but they make use of elaborate data structures that limit their practical use, and they have no easy generalization to directed graphs or two-structures.
---
paper_title: An O ( n 2 ) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs

paper_content:

Abstract This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in O ( n 2 ) time, when n is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, and the restriction of the decomposition to graphs is known as the modular decomposition or substitution decomposition . The decomposition has applications in solving certain scheduling problems and a number of problems on graphs and partial orders. Two algorithms with a comparable time bound have previously been published for undirected graphs, but they make use of elaborate data structures that limit their practical use, and they have no easy generalization to directed graphs or two-structures.
---
paper_title: An O ( n 2 ) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs

paper_content:

Abstract This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in O ( n 2 ) time, when n is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, and the restriction of the decomposition to graphs is known as the modular decomposition or substitution decomposition . The decomposition has applications in solving certain scheduling problems and a number of problems on graphs and partial orders. Two algorithms with a comparable time bound have previously been published for undirected graphs, but they make use of elaborate data structures that limit their practical use, and they have no easy generalization to directed graphs or two-structures.
---
paper_title: An O ( n 2 ) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs

paper_content:

Abstract This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in O ( n 2 ) time, when n is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, and the restriction of the decomposition to graphs is known as the modular decomposition or substitution decomposition . The decomposition has applications in solving certain scheduling problems and a number of problems on graphs and partial orders. Two algorithms with a comparable time bound have previously been published for undirected graphs, but they make use of elaborate data structures that limit their practical use, and they have no easy generalization to directed graphs or two-structures.
---
paper_title: Substitution Decomposition on Chordal Graphs and Applications

paper_content:

In this paper, we present a linear time algorithm for substitution decomposition on chordal graphs. Based on this result, we develop a linear time algorithm for transitive orientation on chordal comparability graphs. Which reduces the complexity of chordal comparability recognition from O(n2) to O(n+m). We also devise a simple linear time algorithm for interval graph recognition where no complicated data structure is involved.
---
paper_title: Computing common intervals of K permutations, with applications to modular decomposition of graphs

paper_content:

We introduce a new way to compute common intervals of K permutations based on a very simple and general notion of generators of common intervals. This formalism leads to simple and efficient algorithms to compute the set of all common intervals of K permutations, that can contain a quadratic number of intervals, as well as a linear space basis of this set of common intervals. Finally, we show how our results on permutations can be used for computing the modular decomposition of graphs in linear time.
---
paper_title: A linear algorithm to decompose inheritance graphs into modules

paper_content:

Inheritance graphs of object-oriented languages can be decomposed into independent subgraphs, or modules, which are inheritance graphs themselves. This paper is devoted to the study of efficient algorithms of decomposition into modules similar to substitution decomposition algorithms. For 2-connected inheritance graphs we search for maximal modules (under inclusion), whereas we show that the significant modules of non-2-connected graphs are the biconnected components. For the 2-connected case, a method based upon a property of greedy linear extensions is proposed. However, in both cases a linear-time complexity algorithm is provided to decompose into modules. Furthermore, the algorithm can be inserted into the inheritance mechanism (such as in CLOS [14]).
---
paper_title: A Synthesis on Partition Refinement: a useful Routine for Strings, Graphs, Boolean Matrices and Automata

paper_content:

Partition refinement techniques are used in many algorithms. This tool allows efficient computation of equivalence relations and is somehow dual to union-find algorithms. The goal of this paper is to propose a single routine to quickly implement all these already known algorithms and to solve a large class of potentially new problems. Our framework yields to a unique scheme for correctness proofs and complexity analysis. Various examples are presented to show the different ways of using this routine.
---
paper_title: A simple linear time algorithm for cograph recognition

paper_content:

In this paper, we describe a new simple linear time algorithm to recognize cographs. Cographs are exactly the P"4-free graphs (where P"4 denotes the path with 4 vertices). The recognition process works in two steps. First, we use partition refinement techniques to produce a factorizing permutation, i.e., an ordering of the vertices in which the strong modules appear consecutively. Then a very simple test algorithm is provided to check whether the given graph is a cograph, using a single sweep of the permutation obtained in the first step.
---
paper_title: Graph decompositions and factorizing permutations

paper_content:

A factorizing permutation of a given graph is simply a permutation of the vertices in which all decomposition sets appear to be factors. Such a concept seems to play a central role in recent papers dealing with graph decomposition. It is applied here for modular decomposition and we propose a linear algorithm that computes the whole decomposition tree when a factorizing permutation is provided. This algorithm can be seen as a common generalization of Ma and Hsu for modular decomposition of chordal graphs and Habib, Huchard and Spinrad for inheritance graphs decomposition. It also suggests many new decomposition algorithms for various notions of graph decompositions.
---
paper_title: A simple linear time algorithm for cograph recognition

paper_content:

In this paper, we describe a new simple linear time algorithm to recognize cographs. Cographs are exactly the P"4-free graphs (where P"4 denotes the path with 4 vertices). The recognition process works in two steps. First, we use partition refinement techniques to produce a factorizing permutation, i.e., an ordering of the vertices in which the strong modules appear consecutively. Then a very simple test algorithm is provided to check whether the given graph is a cograph, using a single sweep of the permutation obtained in the first step.
---
paper_title: Graph decompositions and factorizing permutations

paper_content:

A factorizing permutation of a given graph is simply a permutation of the vertices in which all decomposition sets appear to be factors. Such a concept seems to play a central role in recent papers dealing with graph decomposition. It is applied here for modular decomposition and we propose a linear algorithm that computes the whole decomposition tree when a factorizing permutation is provided. This algorithm can be seen as a common generalization of Ma and Hsu for modular decomposition of chordal graphs and Habib, Huchard and Spinrad for inheritance graphs decomposition. It also suggests many new decomposition algorithms for various notions of graph decompositions.
---
paper_title: Substitution decomposition for discrete structures and connections with combinatorial optimization

paper_content:

In this paper we deal with the substitution decomposition as known for Boolean functions, set systems and relations. It is shown how combinatorial optimization problems, particularly on graphs, partial orders, project networks, (in-) dependence systems and clutters, naturally lead, under weak assumptions, to this kind of decomposition via certain uniqueness results. We then generalize the common features of this type of decomposition from the special cases to a quite general algebraic level, covering infinite cases, and deduce a general Jordan-Holder theorem as well as uniqeness results for the associated composition tree in this general setting. These results are then reinterpreted for the special cases, and the computational aspects of the substitution decomposition are discussed. Throughout, applications to many problems concerning discrete structures are included, as are connections with other approaches in these fields, in particular the split decomposition.
---
paper_title: Graph Classes: A Survey

paper_content:

Preface 1. Basic Concepts 2. Perfection, Generalized Perfection, and Related Concepts 3. Cycles, Chords and Bridges 4. Models and Interactions 5. Vertex and Edge Orderings 6. Posets 7. Forbidden Subgraphs 8. Hypergraphs and Graphs 9. Matrices and Polyhedra 10. Distance Properties 11. Algebraic Compositions and Recursive Definitions 12. Decompositions and Cutsets 13. Threshold Graphs and Related Concepts 14. The Strong Perfect Graph Conjecture Appendix A. Recognition Appendix B. Containment Relationships Bibliography Index.
---
paper_title: Computing common intervals of K permutations, with applications to modular decomposition of graphs

paper_content:

We introduce a new way to compute common intervals of K permutations based on a very simple and general notion of generators of common intervals. This formalism leads to simple and efficient algorithms to compute the set of all common intervals of K permutations, that can contain a quadratic number of intervals, as well as a linear space basis of this set of common intervals. Finally, we show how our results on permutations can be used for computing the modular decomposition of graphs in linear time.
---
paper_title: Algorithmic graph theory and perfect graphs

paper_content:

Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails. The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition. New edition of the "Classic" book on the topic Wonderful introduction to a rich research area Leading author in the field of algorithmic graph theory Beautifully written for the new mathematician or computer scientist Comprehensive treatment
---
paper_title: Restricted permutations and the wreath product

paper_content:

Restricted permutations are those constrained by having to avoid subsequences ordered in various prescribed ways. A closed set is a set of permutations all satisfying a given basis set of restrictions. A wreath product construction is introduced and it is shown that this construction gives rise to a number of useful techniques for deciding the finite basis question and solving the enumeration problem. Several applications of these techniques are given.
---
paper_title: Common Intervals of Multiple Permutations

paper_content:

Given k permutations of n elements, a k-tuple of intervals of these permutations consisting of the same set of elements is called a common interval. We present an algorithm that finds in a family of k permutations of n elements all z common intervals in optimal O(kn+z) time and O(n) additional space. Additionally, we show how to adapt this algorithm to multichromosomal and circular permutations. ::: ::: This extends a result by Uno and Yagiura (Algorithmica 26:290–309, 2000) who present an algorithm to find all z common intervals of k=2 (regular) permutations in optimal O(n+z) time and O(n) space. To achieve our result, we introduce the set of irreducible intervals, a generating subset of the set of all common intervals of k permutations.
---
paper_title: Longest Common Separable Pattern Among Permutations

paper_content:

In this paper, we study the problem of finding the longest common separable pattern among several permutations. We first give a polynomial-time algorithm when the number of input permutations is fixed and next show that the problem is NP-hard for an arbitrary number of input permutations even if these permutations are separable. ::: ::: On the other hand, we show that the NP-hard problem of finding the longest common pattern between two permutations cannot be approximated better than within a ratio of √opt (where opt is the size of an optimal solution) when taking common patterns belonging to patternavoiding permutation classes.
---
paper_title: Fast Algorithms to Enumerate All Common Intervals of Two Permutations

paper_content:

Given two permutations of n elements, a pair of intervals of these permutations consisting of the same set of elements is called a commoninterval . Some genetic algorithms based on such common intervals have been proposed for sequencing problems and have exhibited good prospects. In this paper we propose three types of fast algorithms to enumerate all common intervals: (i) a simple O(n 2 ) time algorithm (LHP), whose expected running time becomes O(n) for two randomly generated permutations, (ii) a practically fast O(n 2 ) time algorithm (MNG) using the reverse Monge property, and (iii) an O(n+K) time algorithm (RC), where K\((\leq {n \choose 2})\) is the number of common intervals. It will also be shown that the expected number of common intervals for two random permutations is O(1) . This result gives a reason for the phenomenon that the expected time complexity O(n) of the algorithm LHP is independent of K . Among the proposed algorithms, RC is most desirable from the theoretical point of view; however, it is quite complicated compared with LHP and MNG. Therefore, it is possible that RC is slower than the other two algorithms in some cases. For this reason, computational experiments for various types of problems with up to n=10 6 are conducted. The results indicate that (i) LHP and MNG are much faster than RC for two randomly generated permutations, and (ii) MNG is rather slower than LHP for random inputs; however, there are cases in which LHP requires Ω(n 2 ) time, but MNG runs in o(n 2 ) time and is faster than both LHP and RC.
---
paper_title: Simple permutations and pattern restricted permutations

paper_content:

A simple permutation is one that does not map any non-trivial interval onto an interval. It is shown that, if the number of simple permutations in a pattern restricted class of permutations is finite, the class has an algebraic generating function and is defined by a finite set of restrictions. Some partial results on classes with an infinite number of simple permutations are given. Examples of results obtainable by the same techniques are given; in particular it is shown that every pattern restricted class properly contained in the 132-avoiding permutations has a rational generating function.
---
paper_title: Common intervals and sorting by reversals: a marriage of necessity

paper_content:

This paper revisits the problem of sorting by reversals with tools developed in the context of detecting common intervals. Mixing the two approaches yields new definitions and algorithms for the reversal distance computations, that apply directly on the original permutation. Traditional constructions such as recasting the signed permutation as a positive permutation, or traversing the overlap graph to analyze its connected components, are replaced by elementary definitions in terms of intervals of the permutation. This yields simple linear time algorithms that identify the essential features in a single pass over the permutation and use only simple data structures like arrays and stacks. Contact: stoye@TechFak.Uni-Bielefeld.DE
---
paper_title: A more efficient algorithm for perfect sorting by reversals

paper_content:

We describe a new algorithm for the problem of perfect sorting a signed permutation by reversals. The worst-case time complexity of this algorithm is parameterized by the maximum prime degree d of the strong interval tree, i.e., f(d).n^O^(^1^). This improves the best known algorithm which complexity was based on a parameter always larger than or equal to d.
---
paper_title: Invitation to fixed-parameter algorithms

paper_content:

PART I: FOUNDATIONS 1. Introduction to Fixed-Parameter Algorithms 2. Preliminaries and Agreements 3. Parameterized Complexity Theory - A Primer 4. Vertex Cover - An Illustrative Example 5. The Art of Problem Parameterization 6. Summary and Concluding Remarks PART II: ALGORITHMIC METHODS 7. Data Reduction and Problem Kernels 8. Depth-Bounded Search Trees 9. Dynamic Programming 10. Tree Decompositions of Graphs 11. Further Advanced Techniques 12. Summary and Concluding Remarks PART III: SOME THEORY, SOME CASE STUDIES 13. Parameterized Complexity Theory 14. Connections to Approximation Algorithms 15. Selected Case Studies 16. Zukunftsmusik References Index
---
paper_title: Polynomial kernels for 3-leaf power graph modification problems

paper_content:

A graph G=(V,E) is a 3-leaf power iff there exists a tree T the leaf set of which is V and such that [email protected]?E iff u and v are at distance at most 3 in T. The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion are FPT when parameterized by the size of the edge set modification. However, polynomial kernels were known for none of these three problems. For each of them, we provide kernels with O(k^3) vertices that can be computed in linear time. We thereby answer an open problem first mentioned by Dom et al. (2004) [8].
---
paper_title: A more effective linear kernelization for cluster editing

paper_content:

In the NP-hard Cluster Editing problem, we have as input an undirected graph G and an integer k>=0. The question is whether we can transform G, by inserting and deleting at most k edges, into a cluster graph, that is, a union of disjoint cliques. We first confirm a conjecture by Michael Fellows [IWPEC 2006] that there is a polynomial-time kernelization for Cluster Editing that leads to a problem kernel with at most 6k vertices. More precisely, we present a cubic-time algorithm that, given a graph G and an integer k>=0, finds a graph G^' and an integer k^'@?k such that G can be transformed into a cluster graph by at most k edge modifications iff G^' can be transformed into a cluster graph by at most k^' edge modifications, and the problem kernel G^' has at most 6k vertices. So far, only a problem kernel of 24k vertices was known. Second, we show that this bound for the number of vertices of G^' can be further improved to 4k vertices. Finally, we consider the variant of Cluster Editing where the number of cliques that the cluster graph can contain is stipulated to be a constant d>0. We present a simple kernelization for this variant leaving a problem kernel of at most (d+2)k+d vertices.
---
paper_title: Fixed-parameter tractability of graph modification problems for hereditary properties

paper_content:

This paper is concerned with the fixed-parameter tractability of the problem of deciding whether a graph can be made into a graph with a specified hereditary property by deleting at most i vertices, at most j edges, and adding at most k edges, where i, j, k are fixed integers. It is shown that this problem is fixed-parameter tractable whenever the hereditary property can be characterized by a finite set of forbidden induced subgraphs. Furthermore, the problem of deciding whether a graph can be made into a chordal graph by adding a fixed number k of edges is shown to be solvable in 0( 4’( k + 1) --3’2 (m + n) ) time, and is thus fixed-parameter tractable.
---
paper_title: An improved fixed-parameter algorithm for minimum-flip consensus trees

paper_content:

In computational phylogenetics, the problem of constructinga consensus tree for a given set of input trees has frequently been addressed.In this paper we study the Minimum-Flip Problem: the inputtrees are transformed into a binary matrix, and we want to find a perfectphylogeny for this matrix using a minimum number of flips, that is,corrections of single entries in the matrix. In its graph-theoretical formulation,the problem is as follows: Given a bipartite graph G = (Vt∪Vc, E),the problem is to find a minimum set of edge modifications such that theresulting graph has no induced path with four edges which starts andends in Vt. ::: ::: We present a fixed-parameter algorithm for the Minimum-Flip Problemwith running time O(4.83k (m+n)+mn) for n taxa, m characters,and k flips. Additionally, we discuss several heuristic improvements. Wealso report computational results on phylogenetic data.
---
paper_title: Efficient parameterized preprocessing for cluster editing

paper_content:

In the Cluster Editing problem, a graph is to be changed to a disjoint union of cliques by at most k operations of edge insertion or edge deletion. Improving on the best previously known quadratic-size polynomial-time kernelization, we describe how a crown-type structural reduction rule can be used to obtain a 6k kernelization bound.
---
paper_title: Fully-dynamic recognition algorithm and certificate for directed cographs

paper_content:

This paper presents an optimal fully-dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in $\mathcal{O}(d)$ time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular tree decomposition is updated; otherwise, a certificate is returned within the same complexity.
---
paper_title: The computational complexity of the role assignment problem

paper_content:

A graph $G$ is $R$-role assignable if there is a locally surjective homomorphism from $G$ to $R$, i.e. a vertex mapping $r:V_G\to V_R$, such that the neighborhood relation is preserved: $r(N_G(u)) = N_R(r(u))$. Kristiansen and Telle conjectured that the decision problem whether such a mapping exists is an {\sf NP}-complete problem for any connected graph $R$ on at least three vertices. In this paper we prove the conjecture and show further corollaries for disconnected graphs and related problems.
---
paper_title: Algorithmic Aspects of a General Modular Decomposition Theory

paper_content:

A new general decomposition theory inspired from modular graph decomposition is presented. This helps unifying modular decomposition on different structures, including (but not restricted to) graphs. Moreover, even in the case of graphs, the terminology ``module'' not only captures the classical graph modules but also allows to handle 2-connected components, star-cutsets, and other vertex subsets. The main result is that most of the nice algorithmic tools developed for modular decomposition of graphs still apply efficiently on our generalisation of modules. Besides, when an essential axiom is satisfied, almost all the important properties can be retrieved. For this case, an algorithm given by Ehrenfeucht, Gabow, McConnell and Sullivan 1994 is generalised and yields a very efficient solution to the associated decomposition problem.
---

Title: A survey on algorithmic aspects of modular decomposition

Section 1: Introduction
Description 1: Provide an overview of modular decomposition, its historical context, combinatorial applications, and the purpose of the paper.

Section 2: Partitive families
Description 2: Introduce the main concepts and theorems of partitive family theory, and discuss its application to the modular decomposition of graphs.

Section 3: Factoring Permutations
Description 3: Explore the concept of factoring permutations and its significance in modular decomposition algorithms and other applications.

Section 4: Modules of a graph
Description 4: Focus on the definition and properties of modules in undirected graphs and the notion of strong modules. 

Section 5: Prime graphs
Description 5: Discuss the structural properties of prime graphs, their importance, and related theorems.

Section 6: Totally decomposable graphs
Description 6: Describe the concept of totally decomposable graphs, known as cographs, and their properties and characterizations.

Section 7: Bibliographic notes
Description 7: Review key literature and survey papers on modular decomposition, highlighting significant contributions and developments in this field.

Section 8: Cographs recognition algorithms as an appetizer
Description 8: Present the Corneil, Pearl, and Stewart's algorithm for cograph recognition and briefly outline a fully dynamic version for edge modifications.

Section 9: Partition refinement
Description 9: Introduce the partition refinement algorithmic technique and its application to compute modular partitions in graphs.

Section 10: Recursive computation of the modular decomposition tree
Description 10: Explain the Ehrenfeucht et al.'s skeleton algorithm and its further simplifications and improvements for computing the modular decomposition tree.

Section 11: Factoring permutation algorithm
Description 11: Detail the process of computing a factoring permutation for a graph and transforming it into a modular decomposition tree.

Section 12: Three novel applications of the modular decomposition
Description 12: Demonstrate the use of modular decomposition in pattern matching, comparative genomics, and parameterized complexity problems.

Section 13: Conclusions and perspectives
Description 13: Summarize the survey and discuss open problems and future research directions in the field of modular decomposition.