Finding scores in tournaments

Balasubramanian, R. ; Raman, Venkatesh ; Srinivasaragavan, G. (1997) Finding scores in tournaments Journal of Algorithms, 24 (2). pp. 380-394. ISSN 0196-6774

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1006/jagm.1997.0865

Abstract

A tournament Tn is an orientation of the complete graph on nvertices. We continue the algorithmic study initiated by 10 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 k( ≤ (n − 1)/2) in Tn is Θ(nk). This 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 directed/undirected graphs. These bounds generalize the classical bound of 11 for finding a sink (a vertex of outdegree 0 and indegree n − 1) in a directed graph.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:72399
Deposited On:04 Jul 2012 03:39
Last Modified:04 Jul 2012 03:39

Repository Staff Only: item control page