{"id":{"repo_id":"msu","oai_identifier":"oai:d.lib.msu.edu:etd_6733"},"canonical_url":"https://search.ndltd.org/etd/msu/oai:d.lib.msu.edu:etd_6733","repository":{"repo_id":"msu","name":"Michigan State University","base_url":"https://d.lib.msu.edu/oai"},"display":{"title":"Distance preserving graphs","abstract":"\"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.","abstract_html":"&quot;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.&quot;--Page ii.","abstract_has_math":false,"creators":["Zahedi, Emad"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Sagan, Bruce E.","Esfahanian, Abdol H.","Hall, Jonathan I.","Bell, Robert W.","Torng, Eric"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017","date_published":"2017","updated_at":"2026-11-18T19:00:47Z","subjects":["Isometrics (Mathematics)","Graphic methods","Graph theory"],"languages":["English"],"rights":["In Copyright"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:6733","isbn:9780355186642","isbn:0355186640","oclc:1028049632","umi:10620487","local:Zahedi_grad.msu_0128D_15558"],"render_values":[{"text":"etd:6733","href":null,"code":true},{"text":"isbn:9780355186642","href":null,"code":true},{"text":"isbn:0355186640","href":null,"code":true},{"text":"oclc:1028049632","href":null,"code":true},{"text":"umi:10620487","href":null,"code":true},{"text":"local:Zahedi_grad.msu_0128D_15558","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://doi.org/doi:10.25335/6h29-qk93","outbound_label":"DOI","outbound_source":"dc:identifier","record_url":"https://doi.org/doi:10.25335/6h29-qk93","record_label":"Repository record","record_kind":"doi","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://d.lib.msu.edu/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Ad.lib.msu.edu%3Aetd_6733","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Sagan, Bruce E.","Esfahanian, Abdol H.","Hall, Jonathan I.","Bell, Robert W.","Torng, Eric"]},{"key":"dc:creator","label":"Author","values":["Zahedi, Emad"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017"]},{"key":"dc:relation","label":"Dc Relation","values":["Electronic Theses & Dissertations"]},{"key":"dc:type","label":"Dc Type","values":["Text","Theses"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Isometrics (Mathematics)","Graphic methods","Graph theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:6733","isbn:9780355186642","isbn:0355186640","oclc:1028049632","umi:10620487","local:Zahedi_grad.msu_0128D_15558","https://doi.org/doi:10.25335/6h29-qk93"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"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.","(Ph. D.)--Michigan State University. Mathematics, 2017","Includes bibliographical references (pages 65-67)"]},{"key":"dc:format","label":"Dc Format","values":["ix, 67 pages","application/pdf"]},{"key":"dc:title","label":"Title","values":["Distance preserving graphs"]}]}],"canonical_facts":{"dc:contributor":["Sagan, Bruce E.","Esfahanian, Abdol H.","Hall, Jonathan I.","Bell, Robert W.","Torng, Eric"],"dc:creator":["Zahedi, Emad"],"dc:date":["2017"],"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.","(Ph. D.)--Michigan State University. Mathematics, 2017","Includes bibliographical references (pages 65-67)"],"dc:format":["ix, 67 pages","application/pdf"],"dc:identifier":["etd:6733","isbn:9780355186642","isbn:0355186640","oclc:1028049632","umi:10620487","local:Zahedi_grad.msu_0128D_15558","https://doi.org/doi:10.25335/6h29-qk93"],"dc:language":["English"],"dc:relation":["Electronic Theses & Dissertations"],"dc:rights":["In Copyright"],"dc:subject":["Isometrics (Mathematics)","Graphic methods","Graph theory"],"dc:title":["Distance preserving graphs"],"dc:type":["Text","Theses"]},"updated_at":"2026-11-18T19:00:47Z"}