کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418356 | 681656 | 2013 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Quasi-hamiltonian paths in semicomplete multipartite digraphs Quasi-hamiltonian paths in semicomplete multipartite digraphs](/preview/png/418356.png)
A quasi-hamiltonian path in a semicomplete multipartite digraph DD is a path which visits each maximal independent set (also called a partite set) of DD at least once. This is a generalization of a hamiltonian path in a tournament.In this paper we investigate the complexity of finding a quasi-hamiltonian path, in a given semicomplete multipartite digraph, from a prescribed vertex xx to a prescribed vertex yy as well as the complexity of finding a quasi-hamiltonian path whose end vertices belong to a given set of two vertices {x,y}{x,y}. While both of these problems are polynomially solvable for semicomplete digraphs (here all maximal independent sets have size one), we prove that the first problem is NP-complete and describe a polynomial algorithm for the latter problem.
Journal: Discrete Applied Mathematics - Volume 161, Issues 7–8, May 2013, Pages 889–898