Catalogo dei prodotti della ricerca
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 Directed Path Family is a family of subsets of some finite ground set whose members call be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G Such that each word ill the language is the set of arcs of some path in G, is a polynomial-time solvable problem. (C) 2009 Elsevier B.V. All rights reserved.
On the complexity of recognizing directed path families / N., Apollonio; Franciosa, Paolo Giulio. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 157:11(2009), pp. 2525-2535. [10.1016/j.dam.2009.03.006]
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | On the complexity of recognizing directed path families | |
| Autori: | ||
| Data di pubblicazione: | 2009 | |
| Rivista: | ||
| Citazione: | On the complexity of recognizing directed path families / N., Apollonio; Franciosa, Paolo Giulio. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 157:11(2009), pp. 2525-2535. [10.1016/j.dam.2009.03.006] | |
| Handle: | http://hdl.handle.net/11573/48538 | |
| Appartiene alla tipologia: | 01a Articolo in rivista |
File allegati a questo prodotto
http://hdl.handle.net/11573/48538
Copyright © 2021