Benvenuti nell'Anagrafe della Ricerca d'Ateneo
La valutazione delle attività di ricerca che si svolgono nelle università ha assunto un'importanza rilevante sia per l'intero sistema universitario sia all'interno di ogni singolo ateneo. Roma Tre si è quindi dotata di idonei strumenti informativi in grado di supportare al meglio le azioni di monitoraggio e di valutazione delle attività di ricerca svolte nei propri dipartimentied ha realizzato una Anagrafe della Ricerca di Ateneo.
EnglishIn this paper we show that the problem of finding a chordless path between a vertex s and a vertex t containing a vertex v remains NP-complete in bipartite graphs, thereby strengthening the previous results on the same problem. We show a relation between this problem and two interval operators: the simple path interval operator in hypergraphs and the even-chorded path interval operator in graphs. We show that the problem of computing the two mentioned intervals is NP-complete.
Mezzini M (2010). On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs. THEORETICAL COMPUTER SCIENCE, 411(7-9), 1212-1220 [10.1016/j.tcs.2009.12.017].
| Titolo: | On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs | |
| Autori: | ||
| Data di pubblicazione: | 2010 | |
| Rivista: | ||
| Citazione: | Mezzini M (2010). On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs. THEORETICAL COMPUTER SCIENCE, 411(7-9), 1212-1220 [10.1016/j.tcs.2009.12.017]. | |
| Abstract: | In this paper we show that the problem of finding a chordless path between a vertex s and a vertex t containing a vertex v remains NP-complete in bipartite graphs, thereby strengthening the previous results on the same problem. We show a relation between this problem and two interval operators: the simple path interval operator in hypergraphs and the even-chorded path interval operator in graphs. We show that the problem of computing the two mentioned intervals is NP-complete. | |
| Handle: | http://hdl.handle.net/11590/139288 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11590/139288
Copyright © 2021