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

### Read

No readable version available.

### Borrow

Find a physical copy near you — powered by WorldCat

**help**?

##
**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 Created December 11, 2009 · 2 revisions 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 |