Quasi-hamiltonian paths in semicomplete multipartite digraphs

DOI10.1016/j.dam.2012.12.003zbMath1262.05095OpenAlexW1998496053MaRDI QIDQ1949094

Sven Simonsen, Alessandro Maddaloni, Jörgen Bang-Jensen

Publication date: 25 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.12.003

zbMATH Keywords

polynomial algorithmNP-completemultipartite tournamentsemicomplete multipartite digraphextended semicomplete digraphquasi-hamiltonian path

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (3)

\(\mathrm{Quasi}_{\mathrm{ps}}\)-pancyclicity of regular multipartite tournament ⋮ Tournaments and Semicomplete Digraphs ⋮ Semicomplete Multipartite Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Weakly quasi-Hamiltonian-set-connected multipartite tournaments
• Hamiltonian-connected tournaments
• Vertex deletion and cycles in multipartite tournaments
• Weakly Hamiltonian-connected ordinary multipartite tournaments
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
• Generalizations of tournaments: A survey
• One-diregular subgraphs in semicomplete multipartite digraphs
• Color-coding
• Finding a Longest Path in a Complete Multipartite Digraph
• Digraphs
• Aggregating inconsistent information

This page was built for publication: Quasi-hamiltonian paths in semicomplete multipartite digraphs