Back to search

Michigan State University

Distance preserving graphs

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 × 3

Rights

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

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Zahedi, Emad. Distance preserving graphs. 2017. https://doi.org/doi:10.25335/6h29-qk93