Finding a Longest Path in a Complete Multipartite Digraph

DOI10.1137/0406020MaRDI QIDQ4695387zbMATH OpenOpenAlexFDO

Authors G. Gutin

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

zbMATH Keywords

digraphHamiltonian pathlongest pathpolynomial algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Longest paths in semicomplete multipartite digraphs
• Longest paths through an arc in strong semicomplete multipartite digraphs
• scientific article; zbMATH DE number 3979087
• scientific article; zbMATH DE number 4101247
• Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs

Cited in

(33)

• Partial and perfect path covers of cographs
• Longest paths in semicomplete multipartite digraphs
• 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
• Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs
• Weakly Hamiltonian-connected ordinary multipartite tournaments
• Longest paths through an arc in strong semicomplete multipartite digraphs
• Quasi-hamiltonian paths in semicomplete multipartite digraphs
• 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
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Multipartite tournaments: a survey
• An approximation algorithm for the longest cycle problem in solid grid graphs
• An approximation algorithm for the longest path problem in solid grid graphs
• Semicomplete Multipartite Digraphs
• scientific article; zbMATH DE number 3948312 (Why is no real title available?)
• scientific article; zbMATH DE number 3979087 (Why is no real title available?)
• scientific article; zbMATH DE number 4047757 (Why is no real title available?)
• On finding the longest antisymmetric path in directed acyclic graphs
• Longest (s, t)-paths in L-shaped grid graphs
• Solution of a conjecture of Volkmann on the number of vertices in longest paths and cycles of strong semicomplete multipartite digraphs
• Ramsey-type results for path covers and path partitions. II: Digraphs
• The longest path problem in odd-sized O-shaped grid graphs
• Generalized paths and cycles in semicomplete multipartite digraphs
• Compositions of digraphs: a survey
• The complexity of color-constrained paths in semicomplete multipartite digraphs
• AI Planning Languages Semantics
• Verified SAT-Based AI Planning
• Upper Bounding Diameters of State Spaces of Factored Transition Systems
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• Used car salesman problem: a differential auction-barter market

This page was built for publication: Finding a Longest Path in a Complete Multipartite Digraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4695387)