CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishA dominating set of a graph G = (N,E) is a subset S of nodes such that every node is either in S or adjacent to a node which is in S. The domatic number of G is the size of a maximum cardinality partition of N into dominating sets. The problems of finding a minimum cardinality dominating set and the domatic number are both NP-complete even for special classes of graphs. In the present paper we give an O(n{divides}E{divides}) time algorithm that finds a minimum cardinality dominating set when G is a circular arc graph (intersection graph of arcs on a circle). The domatic number problem is solved in O(n2 log n) time when G is a proper circular arc graph, and it is shown NP-complete for general circular arc graphs
| Autori interni: | |
| Autori: | BONUCCELLI M |
| Titolo: | DOMINATING SETS AND DOMATIC NUMBER OF CIRCULAR ARC GRAPHS |
| Anno del prodotto: | 1985 |
| Digital Object Identifier (DOI): | 10.1016/0166-218X(85)90025-3 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11568/6841
Copyright © 2021