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

complexitytournamentgeneralized paths

Mathematics Subject Classification ID

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

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

(17)

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

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)