PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
From MaRDI portal
Publication:5248997
DOI10.1142/S0129054199000125zbMath1319.68240WikidataQ56016950 ScholiaQ56016950MaRDI QIDQ5248997
Laurent Viennot, Christophe Paul, Michel A. Habib
Publication date: 29 April 2015
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Graph algorithms (graph-theoretic aspects) (05C85) General topics in the theory of algorithms (68W01)
Related Items
Equimatchable claw-free graphs, Applying clique-decomposition for computing Gromov hyperbolicity, An algorithmic view of gene teams, From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, Characteristic invariants in Hennessy-Milner logic, A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs, Polynomial-time recognition of clique-width \(\leq 3\) graphs, Subquadratic-time algorithm for the diameter and all eccentricities on median graphs, Twins in Subdivision Drawings of Hypergraphs, \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs, Partition refinement of component interaction automata, Cograph editing: Merging modules is equivalent to editing P_4s, A survey of the algorithmic aspects of modular decomposition, Generalizing the Paige-Tarjan algorithm by abstract interpretation, Computing \(H\)-joins with application to 2-modular decomposition, An efficient exact algorithm for triangle listing in large graphs, Minimal proper interval completions, A simple linear time algorithm for cograph recognition, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees, Boolean-width of graphs, Parameterized complexity of a coupled-task scheduling problem, Minimal interval completion through graph exploration, A Representation Theorem for Union-Difference Families and Application, Algorithmic aspects of a general modular decomposition theory
Cites Work
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Graphs indecomposable with respect to the X-join
- A linear algorithm to decompose inheritance graphs into modules
- Doubly lexical ordering of dense 0--1 matrices
- On a property of the class of n-colorable graphs
- A Linear Recognition Algorithm for Cographs
- Three Partition Refinement Algorithms
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- Algorithmic Aspects of Vertex Elimination on Graphs
- Partially Ordered Sets
