𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs

✍ Scribed by Christophe Crespelle; Christophe Paul

Publisher
Springer
Year
2009
Tongue
English
Weight
684 KB
Volume
58
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A fully dynamic algorithm for modular de
A fully dynamic algorithm for modular decomposition and recognition of cographs
✍ Ron Shamir; Roded Sharan πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 236 KB

The problem of dynamically recognizing a graph property calls for e ciently deciding if an input graph satisΓΏes the property under repeated modiΓΏcations to its set of vertices and edges. The input to the problem consists of a series of modiΓΏcations to be performed on the graph. The objective is to m

Parallel Algorithms for Hierarchical Clu
Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
✍ Elias Dahlhaus πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 306 KB

We present efficient parallel algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decomposition. We show that efficient parallel split decomposition induces an efficient parallel

An O(n2) Divide-and-Conquer Algorithm fo
An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
✍ A. Ehrenfeucht; H.N. Gabow; R.M. Mcconnell; S.J. Sullivan πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 526 KB

This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in \(O\left(n^{2}\right)\) 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, an

An algorithm for the decomposition of gr
An algorithm for the decomposition of graphs into cliques
✍ Xiang-Ying Su πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 340 KB πŸ‘ 1 views

## Abstract Chung (F. R. K. Chung, On the decomposition of graphs, __SIAM J. Algebraic Discrete Methods__ 23 (1981), 1–12.) and independently GyΓΆri and Kostochka (E. GyΓΆri and A. V. Kostochka, On a problem of G. O. H. Katona and T. TarjΓ‘n, __Acta Math. Acad. Sci. Hung.__ 34 (1979), 321–327.) proved