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 (47)
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
This page was built for publication: Incremental modular decomposition
