Name
Abstract | ||
|---|---|---|
A quasi-hamiltonian path in a semicomplete multipartite digraph D is a path which visits each maximal independent set (also called a partite set) of D 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 x to a prescribed vertex y as well as the complexity of finding a quasi-hamiltonian path whose end vertices belong to a given set of two vertices {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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.dam.2012.12.003 | Discrete Applied Mathematics |
Keywords | Field | DocType |
latter problem,semicomplete multipartite digraph,maximal independent set,hamiltonian path,prescribed vertex,semicomplete digraph,partite set,end vertex,quasi-hamiltonian path,prescribed vertex y,np complete | Discrete mathematics,Tournament,Combinatorics,Multipartite,Vertex (geometry),Hamiltonian (quantum mechanics),Hamiltonian path,Polynomial algorithm,Mathematics,Digraph,Maximal independent set | Journal |
Volume | Issue | ISSN |
161 | 7-8 | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jørgen Bang-Jensen | 1 | 573 | 68.96 |
| Alessandro Maddaloni | 2 | 10 | 2.09 |
| Sven Simonsen | 3 | 9 | 2.09 |