Some relations of subsequences in permutations to graph theory with algorithmic applications
No Thumbnail Available
Date
2015-08-19
Authors
Rotem, D
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The representation of some types of graphs as permutations,
is utilized in devising efficient algorithms on those graphs.
Maximum 'cliques in permutation graphs and circle graphs
are found, by searching for a longest ascending or descending
subsequence in their representing permutation.
The correspondence between n-noded binary trees and
the set SSn of stack-sortable permutations, forms the
basis of an algorithm for generating and indexing such trees.
The-relations between a graph and its representing
p ermutation, are also employed in the proof of theorems
concerning properties of subsequences in this permutation.
In particular, expressions for the average lengths of the
longest ascending and descending subsequence a in a random
member of SSn , and the average number of inversions in such
a permutation, are derived using properties of binary trees.
Finally, a correspondence between the set SSn , and the set
of permutations of order n With no descending subsequence of
length 3, is demonstrated.
Description
A thesis submitted to the Faculty d£ Science of the University
of the Witwatersfand in fulfillment of the requirements for the
degree of Doctor of Philosophy.
Johannesburg, 1977.