Abstract
dc:description"The computational complexity of exploring distance properties of large graphs such as real-world social networks which consist of millions of nodes is extremely expensive. Recomputing distances in subgraphs of the original graph will add to the cost. One way to avoid this is to use subgraphs where the distance between any pair of vertices is the same as in the original graph. Such a subgraph is called isometric. A connected graph is distance preserving, for which we use the abbreviation dp, if it has an isometric subgraph of every order. In this framework we study dp graphs from both the structural and algorithmic perspectives. First, we study the structural nature of dp graphs. This involves classifying graphs based on the dp property and the relation between dp graphs to other graph classes. Second, we study the recognition problem of dp graphs. We intend to develop efficient algorithms for finding isometric subgraphs as well as deciding whether a graph is dp or not."--Page ii.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Zahedi, Emad
- Contributors dc:contributor
-
- Sagan, Bruce E.
- Esfahanian, Abdol H.
- Hall, Jonathan I.
- Bell, Robert W.
- Torng, Eric
Subjects
dc:subject × 3Rights
dc:rights- Statement dc:rights
-
- In Copyright
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
etd:6733
isbn:9780355186642
isbn:0355186640
oclc:1028049632
umi:10620487
local:Zahedi_grad.msu_0128D_15558 - OAI record oai:identifier
- https://d.lib.msu.edu/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Ad.lib.msu.edu%3Aetd_6733