An optimal algorithm recognizing distance-hereditary graphs under a sequence of edge deletions.
Published: 2006
Language: eng
Number of pages: 145
ISBN-13: 9780494161005
Description: A dynamic graph algorithm starts with an input graph, modifies this graph under a series of vertex and edge additions and deletions, and after each modification, determines if some property of the graph continues to hold. This thesis presents the first dynamic graph algorithm for distance-hereditary graphs. The algorithm allows edge deletions, and after each deletion, verifies that the resulting graph is distance-hereditary. The algorithm is optimal in that each deletion can be performed in constant time. In presenting the algorithm the thesis develops conditions under which an edge can be removed from a distance-hereditary graph with the result remaining distance-hereditary, and introduces a new representation for distance-hereditary graphs.
Notes: Source: Masters Abstracts International, Volume: 44-06, page: 2858.

Advisor: D. Corneil.

Thesis (M.Sc.)--University of Toronto, 2006.

Electronic version licensed for access by U. of T. users.

ROBARTS MICROTEXT copy on microfiche.