Finding a Longest Path in a Complete Multipartite Digraph
From MaRDI portal
Publication:4695387
DOI10.1137/0406020zbMath0773.05071OpenAlexW2056724312MaRDI QIDQ4695387
Publication date: 29 June 1997
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0406020
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)
Related Items (18)
An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian ⋮ Vertex heaviest paths and cycles in quasi-transitive digraphs ⋮ Paths and cycles in extended and decomposable digraphs ⋮ Alternating cycles and paths in edge-coloured multigraphs: A survey ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Ramsey-type results for path covers and path partitions. II: Digraphs ⋮ Quasi-hamiltonian paths in semicomplete multipartite digraphs ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ Multipartite tournaments: a survey ⋮ A genetic algorithm for the picture maze generation problem ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs ⋮ An approximation algorithm for the longest path problem in solid grid graphs ⋮ A linear-time algorithm for the longest path problem in rectangular grid graphs ⋮ Partial and perfect path covers of cographs ⋮ Weakly Hamiltonian-connected ordinary multipartite tournaments ⋮ Semicomplete Multipartite Digraphs ⋮ Used car salesman problem: a differential auction-barter market
This page was built for publication: Finding a Longest Path in a Complete Multipartite Digraph
