The complexity of finding generalized paths in tournaments

DOI10.1016/0196-6774(83)90011-1MaRDI QIDQ3315014zbMATH OpenOpenAlexFDO

Authors Moshe Rosenfeld, Pavol Hell

Publication date 1983

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(83)90011-1

zbMATH Keywords

complexitygeneralized pathstournament

Mathematics Subject Classification ID

Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of finding certain trees in tournaments
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
• Finding Scores in Tournaments
• scientific article; zbMATH DE number 1439485
• scientific article; zbMATH DE number 3884197

Cited in

(18)

• A survey on the complexity of tournament solutions
• A linear-time algorithm for finding Hamiltonian cycles in tournaments
• Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs
• Antidirected Hamiltonian paths between specified vertices of a tournament
• A structured family of clustering and tree construction methods
• Pancyclicity in strong k-quasi-transitive digraphs of large diameter
• Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs
• Longest path partitions in generalizations of tournaments
• scientific article; zbMATH DE number 1823770 (Why is no real title available?)
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
• Finding Scores in Tournaments
• The complexity of finding certain trees in tournaments
• Tight bounds for finding degrees from the adjacency matrix
• Sublinear-Time Algorithms for Tournament Graphs
• ON COST-OPTIMAL MERGE OF TWO INTRANSITIVE SORTED SEQUENCES
• Path decompositions of tournaments
• NC algorithms for antidirected hamiltonian paths and cycles in tournaments
• Finding an antidirected Hamiltonian path starting with a forward arc from a given vertex of a tournament

This page was built for publication: The complexity of finding generalized paths in tournaments

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