On a Node Ranking Problem of Trees and Graphs,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 24, 1986
Accession Number
ADA182315

Entities

People

  • Ananth V. Iyer
  • G. Vijayan
  • H. D. Ratliff

Organizations

  • Georgia Tech

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Communication Networks
  • Computer Science
  • Computers
  • Decomposition
  • Diameters
  • Engineering
  • Industrial Engineering
  • Language
  • Mathematics
  • Military Research
  • Polynomials
  • Separators
  • Systems Engineering
  • Trees (Data Structures)

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.