Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments

DOI10.1137/0403002zbMath0686.68052OpenAlexW2033472258WikidataQ56503960 ScholiaQ56503960MaRDI QIDQ4205086

Joseph (Seffi) Naor, Amotz Bar-Noy

Publication date: 1990

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0403002

zbMATH Keywords

sortingparallel computationtournamentsfeedback setscomparison modelHamilton pathsCRCW model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs ⋮ Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows ⋮ A survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Tight bounds for finding degrees from the adjacency matrix ⋮ Query complexity of tournament solutions ⋮ Effective Computation of a Feedback Arc Set Using PageRank ⋮ NC algorithms for antidirected hamiltonian paths and cycles in tournaments ⋮ Paths with many shortcuts in tournaments ⋮ ON COST-OPTIMAL MERGE OF TWO INTRANSITIVE SORTED SEQUENCES ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ A note on the query complexity of the Condorcet winner problem ⋮ Monocular extraction of 2.1D sketch using constrained convex optimization

This page was built for publication: Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments