Finding Scores in Tournaments

✍ Scribed by R Balasubramanian; Venkatesh Raman; G Srinivasaragavan

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 181 KB
• Volume: 24
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0865

✦ Synopsis

A tournament T is an orientation of the complete graph on n vertices. We n w continue the algorithmic study initiated by Hell and Rosenfeld J. Algorithms 4 Ž .

x 1983 , 303᎐309 of recognizing various directed trees in tournaments. Hell and Rosenfeld studied the complexity of finding various oriented paths in tournaments by probing edge directions. Here, we investigate the complexity of finding a vertex Ž . of prescribed outdegree or indegree in the same model. We show that the Ž Ž . .

Ž . complexity of finding a vertex of outdegree

bound is in sharp contrast to the ⌰ n bound for selection in the case of transitive tournaments. We also establish tight bounds for finding vertices of prescribed degree from the adjacency matrix of general directedrundirected graphs. These w bounds generalize the classical bound of King and Smith-Thomas Inform. Process. Ž . .x Ž Lett. 14 1982 , 109᎐111 for finding a sink a vertex of outdegree 0 and indegree . n y 1 in a directed graph.