Incremental modular decomposition
From MaRDI portal
Publication:3823808
DOI10.1145/58562.59300zbMath0671.68030OpenAlexW2056697294WikidataQ127782724 ScholiaQ127782724MaRDI QIDQ3823808
John H. Muller, Jeremy P. Spinrad
Publication date: 1989
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/58562.59300
Related Items
The graph sandwich problem for 1-join composition is NP-complete, Primitive 2-structures with the \((n-2)\)-property, A \(k\)-structure generalization of the theory of 2-structures, The homogeneous set sandwich problem, Note on the homogeneous set sandwich problem, A linear algorithm to decompose inheritance graphs into modules, An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures, On semi-\(P_ 4\)-sparse graphs, Equistable graphs, From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, The discrete time-cost tradeoff problem revisited, A supernodal formulation of vertex colouring with applications in course timetabling, Computation of diameter, radius and center of permutation graphs, Efficient parallel modular decomposition (extended abstract), Scheduling with due date assignment under special conditions on job processing, Cograph editing: Merging modules is equivalent to editing P_4s, A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs, On the closure of triangle-free graphs under substitution, Fully dynamic representations of interval graphs, A survey of the algorithmic aspects of modular decomposition, A fully dynamic algorithm for modular decomposition and recognition of cographs., Upper bounds to the clique width of graphs, Transitive closure for restricted classes of partial orders, Characterization and complexity of uniformly nonprimitive labeled 2-structures, A linear-time recognition algorithm for \(P_{4}\)-reducible graphs, An algorithm for finding homogeneous pairs, Connected domination and Steiner set on weighted permutation graphs, Theory of 2-structures, Peakless functions on graphs, On the calculation of transitive reduction-closure of orders, Bipartite bithreshold graphs, \(P_ 4\)-trees and substitution decomposition, A distance measure for large graphs based on prime graphs, Not complementary connected and not CIS \(d\)-graphs form weakly monotone families, Single machine scheduling with precedence constraints and positionally dependent processing times, Decomposing complete edge-chromatic graphs and hypergraphs. Revisited, Fully dynamic recognition algorithm and certificate for directed cographs, A review of the contribution of operational research to project management, Fully dynamic algorithm for recognition and modular decomposition of permutation graphs, Minimum 2-tuple dominating set of permutation graphs, Optimal procedures for the discrete time/cost trade-off problem in project networks, Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs, An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs, An efficient algorithm to find next-to-shortest path on permutation graphs, Modular decomposition and transitive orientation, Minimum r-neighborhood covering set of permutation graphs, An efficient algorithm for solving the homogeneous set sandwich problem
