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.
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.
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. |
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 |