Open Library logo
New Feature: You can now embed Open Library books on your website!   Learn More
Last edited by WorkBot
January 24, 2010 | History

An optimal algorithm recognizing distance-hereditary graphs under a sequence of edge deletions 1 edition

An optimal algorithm recognizing distance-hereditary graphs under a se ...
Marc Tedder

Prefer the physical book? Check nearby libraries with:


Buy this book


There's no description for this book yet. Can you add one?
There is only 1 edition record, so we'll show it here...  •  Add edition?

An optimal algorithm recognizing distance-hereditary graphs under a sequence of edge deletions.

Published 2006 .
Written in English.

About the Book

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.

Edition 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.

The Physical Object

Pagination
145 leaves.
Number of pages
145

ID Numbers

Open Library
OL19214783M
ISBN 13
9780494161005

History

Download catalog record: RDF / JSON
January 24, 2010 Edited by WorkBot add more information to works
December 11, 2009 Created by WorkBot add works page