Return to search

A fast practical algorithm for the vertex separation of unicyclic graphs

The vertex separation of a graph is the minimum vertex separation of a linear layout of that graph over all its linear layouts. A linear layout of a graph is an arrangement of its vertices in a line and the vertex separation of a linear layout is maximum number of vertices to the left of any intervertex "gap" that are adjacent to vertices to the right of that gap, over all gaps. A unicyclic graph is a connected graph with precisely one cycle that is, a tree plus an extra edge. We present a O(n lgn) algorithm to compute the optimal vertex separation of unicyclic graphs. The algorithm is "practical" in the sense that it is easily implementable. Furthermore, the algorithm outputs a layout for the unicyclic graph of minimum vertex separation.

  1. http://hdl.handle.net/1828/612
Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/612
Date10 April 2008
CreatorsMarkov, Minko Marinov.
ContributorsEllis, John Arthur
Source SetsUniversity of Victoria
Detected LanguageEnglish

Page generated in 0.0018 seconds