Accession Number : ADA182315

Title :   On a Node Ranking Problem of Trees and Graphs,

Corporate Author : GEORGIA INST OF TECH ATLANTA PRODUCTION AND DISTRIBUTION RESEARCH CENTER

Personal Author(s) : Iyer, Ananth V ; Ratliff, H D ; Vijayan, G

PDF Url : ADA182315

Report Date : 24 Oct 1986

Pagination or Media Count : 14

Abstract : We discussed a problem about ranking nodes of a graph, which is a restriction of the general graph coloring problem. A graph is said to have number k if its vertices can be ranked using integers 1,...,k such that if two nodes have the same rank i, there is a node with rank greater than i on every path between the two nodes. We give an O(n log n) algorithm for optimal ranking of trees, and also present bounds on the rank number for trees, planar and other graph classes.

Descriptors :   *NODES, *RANKING, *GRAPHS, ALGORITHMS, COLORING, OPTIMIZATION, TREES, PATHS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE