An optimal algorithm for finding all convex subsets in tournaments

MaRDI QIDQ2760997zbMATH OpenFDO

Authors Marty J. Wolf, David J. Haglin

Publication date 17 December 2001

Published in Ars Combinatoria (Search for Journal in Brave)

zbMATH Keywords

convex settournamenttransitive closure

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

The paper gives an \(O(n^3)\)-time algorithm for finding all convex sets in a tournament. An argument that the algorithm is asymptotically optimal is also given. The method uses a reduction to the transitive closure of a graph where an oriented edge expresses the fact that if the head belongs to a convex set then the same holds for the tail.

Recommendations

• On Convex Subsets in Tournaments
• scientific article; zbMATH DE number 4114666
• Transitive convex subsets in large tournaments
• Algorithms for finding maximum transitive subtournaments
• An optimal algorithm for finding compact sets

Cited in

(5)

• Optimal parallel construction of prescribed tournaments
• Transitive convex subsets in large tournaments
• scientific article; zbMATH DE number 2147941 (Why is no real title available?)
• scientific article; zbMATH DE number 4114666 (Why is no real title available?)
• On Convex Subsets in Tournaments

This page was built for publication: An optimal algorithm for finding all convex subsets in tournaments

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