Computation Of Center And Median Of Graphs: An Algorithmic Approach

Abstract

In the recent years there is an increasing interest among researchers in the design and analysis of algorithms to solve graph-theoretic problems. In this paper, we consider finite, connected, undirected simple graphs with n vertices. We discuss the minimax location problem and maximin location problems and design suitable algorithms to find the centers and medians of graphs.  We design a linear time algorithm to check whether the given tree is a central and a bi-central tree. Also we design an algorithm to test whether the graph G is a unique eccentric graph or not.