Optimal decomposition by clique separators (Q2366013)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 223108
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Optimal decomposition by clique separators |
scientific article; zbMATH DE number 223108 |
Statements
Optimal decomposition by clique separators (English)
0 references
29 June 1993
0 references
Decompositions of graphs by means of clique separators have been studied by \textit{R. E. Tarjan} [Discrete Math. 55, 221-232 (1985; Zbl 0572.05039)] and others, and have many applications. These decompositions are not generally unique. The author introduces a particular kind of decomposition by clique separators which does result in a unique set of final graphs---these being the maximal subgraphs themselves free of clique separators. He also modifies the algorithm of Tarjan to produce this special decomposition, in time \(O(mn)\).
0 references
prime subgraphs
0 references
clique separators
0 references
decompositions
0 references
0 references
0 references
0 references
0.8911771178245544
0 references
0.8886457085609436
0 references
0.872963547706604
0 references
0.862517237663269
0 references
0.8414932489395142
0 references
