
An extended locally semicomplete digraph, or extended LSD for short, is a digraph that can be obtained from locally semicomplete digraphs by substituting independent sets for vertices. The paper characterizes Hamiltonian extended LSDs as well as extended LSDs containing Hamiltonian paths, implying polynomial algorithms for finding a longest path and a longest cycle in an extended LSD. It is shown that the longest path problem is polynomially solvable for totally \(\Phi_0\)-decomposable digraphs. Similar results are obtained for the longest cycle problem and other problems on cycles in subfamilies of totally \(\Phi_0\)-decomposable digraphs.
Directed graphs (digraphs), tournaments, Faculty of Science\Computer Science, longest path problem, digraph, 004, 510, Theoretical Computer Science, longest cycle problem, Discrete Mathematics and Combinatorics, Paths and cycles, Hamiltonian paths
Directed graphs (digraphs), tournaments, Faculty of Science\Computer Science, longest path problem, digraph, 004, 510, Theoretical Computer Science, longest cycle problem, Discrete Mathematics and Combinatorics, Paths and cycles, Hamiltonian paths
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 11 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
