The modular decomposition of a graph or relation has a large number of combinatorial applications. It divides the structure into a set of "prime" induced substructures, which cannot be further decomposed. Recent work on graphs and k-ary relations has focused on the discovery that prime induced substructures are densely nested when they occur. Lower bounds on the "nesting density" of prime substructures in graphs are used heavily in the only known linear-time algorithm for directed graphs. We improve on the previously known lower bounds for k-ary relations, and show that no further improvement is possible. © 2001 Elsevier Science B.V. All rights reserved.

Bonizzoni, P., Mcconnel, R. (1999). Nesting of Indecomposable Substructures in k-ary relations. THEORETICAL COMPUTER SCIENCE, 259(1-2), 341-357 [10.1016/S0304-3975(00)00017-7].

Nesting of Indecomposable Substructures in k-ary relations

BONIZZONI, PAOLA;
1999

Abstract

The modular decomposition of a graph or relation has a large number of combinatorial applications. It divides the structure into a set of "prime" induced substructures, which cannot be further decomposed. Recent work on graphs and k-ary relations has focused on the discovery that prime induced substructures are densely nested when they occur. Lower bounds on the "nesting density" of prime substructures in graphs are used heavily in the only known linear-time algorithm for directed graphs. We improve on the previously known lower bounds for k-ary relations, and show that no further improvement is possible. © 2001 Elsevier Science B.V. All rights reserved.
Articolo in rivista - Articolo scientifico
nesting, indecomposable, substructures, ary
English
341
357
17
Bonizzoni, P., Mcconnel, R. (1999). Nesting of Indecomposable Substructures in k-ary relations. THEORETICAL COMPUTER SCIENCE, 259(1-2), 341-357 [10.1016/S0304-3975(00)00017-7].
Bonizzoni, P; Mcconnel, R
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/34076
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact