Finding the two-core of a tree

Ronald I. Becker, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

The 1-core of a graph is a path minimizing the sum of the distances of all vertices of the graph from the path. A linear algorithm for finding a 1-core of a tree was presented by Morgan and Slater. The problem for general graphs is NP-hard. A 2-core of a graph is a set of two paths minimizing the sum of the distances of all vertices of the graph from any of the two paths. We consider both cases of disjoint paths and intersecting paths for a tree. Interesting relations between 1-core and 2-core of a tree are found. These relations imply two efficient algorithms for finding the 2-core. The complexity of these algorithms is O(|V|2) and O(|V| · d(T)), respectively, where d(T) is the number of edges in the diameter of the tree. The algorithms are applicable for routing highways in a system of roads. A w-point core is a path minimizing the sum of the distances of all vertices of the graph from either the vertex w or the path. A linear algorithm for finding a w-point core of a tree is presented. It is applied as a procedure in the second algorithm for the 2-core.

Original languageEnglish (US)
Pages (from-to)103-113
Number of pages11
JournalDiscrete Applied Mathematics
Volume11
Issue number2
DOIs
StatePublished - Jun 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Finding the two-core of a tree'. Together they form a unique fingerprint.

Cite this