{"id":{"repo_id":"msu","oai_identifier":"oai:d.lib.msu.edu:etd_51183"},"canonical_url":"https://search.ndltd.org/etd/msu/oai:d.lib.msu.edu:etd_51183","repository":{"repo_id":"msu","name":"Michigan State University","base_url":"https://d.lib.msu.edu/oai"},"display":{"title":"Graph mutation, graph distance, and graph gradient","abstract":"Most networks constantly change, and predicting links or recovering from link failures is crucial for maintaining a network. Distance-based graph invariants are important criteria for network maintenance. A graph mutation is a change in the edge set of a graph, and a graph gradient is the change in a graph invariant after a mutation. We present the general concepts of discrete integral and derivative for vertex and edge weighted graphs as a tool. Using the concepts, some related problems are solved more efficiently, flexibly, and simpler than the existing solutions.Let G=(V(G), E(G)) be a graph with vertex weight function f_G and edge weight function w_G. And d_G (u,v) denotes the distance of u,v∈V(G), the minimum sum of edge weights across all the paths connecting u and v. Then assumeW_(α,β) (G)=∑_({u,v}⊆V(G))[αf_G⁡(u) ×f_G(v)+β(f_G⁡(u) +f_G⁡(v)) ] d_G (u,v) , α,β∈R, and T is a spanning tree (ST) of G. If an edge e∈E(T) fails, it creates T-e with two components. If T-e reconnected with ε∈E(G)\\E(T) and form T_(ε\\e)=T+ε-e such that W_(α,β) (T_(ε\\e)) is minimum, then ε is a best swap edge (BSE) of e w.r.t W_( α,β). We devise an algorithm that finds a BSE ε∈E(G)\\E(T) w.r.t W_( α,β) for each e∈E(T) and computes W_( α,β) (T_(ε\\e) ). We call the algorithm \"all best swap edges w.r.t. W_( α,β)\"(ABSEW). Preprocessing for ABSEW takes O(n)-time, whereas solving ABSEW has an average time-complexity of O((m-n)log n) and a best time-complexity of O(m-n), all in O(m)-space, where (m,n)=(|E(G)|,|V(G)|). For dense graphs, however, the average time reaches O(m-n). T's routing cost (RC) for a given set of sources S⊆ V(G) equals ∑_((a,b)∈V(T)×S )d_T (u,v). For 2-edge-connected positively edge-weighted graphs and some specified |S|, researchers have found a BSE for each edge of an ST w.r.t. RC. The solutions have time complexities of O(m2^O(α(2m,2m)) .log^2 n) (|S|=O(1) or n), O(m.log n+n^2 ) (|S|=2), and O(mn) (|S|>2) for the specified |S|'s. Our algorithm outperforms existing algorithms regarding RC with no limit on |S|, edge and vertex weights, or graph type, while also computing the RC for each BSE. Assume T is a positively weighted n-vertex tree, and e∈ E(T) fails. If we reconnect the components of T-e with ε∈E(T^c) such that, W_( α,β) (T_(ε\\e) ) is minimum, then ε is called a best switch (BS) of e w.r.t. W_(α,β). For the inputs e∈ E(T) and w,α,β ∈R^+, we find ε, T_(ε\\e), and W_(α,β) (T_(ε\\e) ) with the worst average time of O(log⁡〖n)〗 and the best average time of O(1) where ε is a BS of e w.r.t. W_(α,β) and the weight of ε is w. There are comparable algorithms to ours only w.r.t W_( 1,0) or W_( 0,1) which are relatively complicated and limited. In our algorithm α,β can be changed at any step without affecting complexities or preprocessing.A subgraph H of a simple graph G is isomeric if d_G (u,v)=d_H (u,v), ∀u,v∈V(H). And G is distance-preserving if it has at least a k-vertex isometric subgraph for each k, 1≤k≤|V(G)|. There is a relatively old conjecture by Nussbaum and Esfahanian that says: if deg_G (v)>n/2, ∀v∈V(G), then G is distance-preserving. We will have a close asymptotic approach to the conjecture.One added edge to a simple graph G (w_G=1) is called inset edge and mutates G. Establishing some regular and extensive matrix tools, we devised an algorithm that computes and sorts the gradient of the inset edges of a tree regarding the total distance, D(G)=∑_({u,v}⊆V(G))d_G (u,v) for G. The algorithms' average time complexity is minimal, reducing the previous algorithm from O(n^5) to an average of n^2 O(log⁡n), where n=|V(G)|. Indeed, we compute the total distance of O(n^2) unicyclic graphs each on average of O(log⁡n)-time and the best time of O(1).","abstract_html":"Most networks constantly change, and predicting links or recovering from link failures is crucial for maintaining a network. Distance-based graph invariants are important criteria for network maintenance. A graph mutation is a change in the edge set of a graph, and a graph gradient is the change in a graph invariant after a mutation. We present the general concepts of discrete integral and derivative for vertex and edge weighted graphs as a tool. Using the concepts, some related problems are solved more efficiently, flexibly, and simpler than the existing solutions.Let G=(V(G), E(G)) be a graph with vertex weight function f_G and edge weight function w_G. And d_G (u,v) denotes the distance of u,v∈V(G), the minimum sum of edge weights across all the paths connecting u and v. Then assumeW_(α,β) (G)=∑_({u,v}⊆V(G))[αf_G⁡(u) ×f_G(v)+β(f_G⁡(u) +f_G⁡(v)) ] d_G (u,v) , α,β∈R, and T is a spanning tree (ST) of G. If an edge e∈E(T) fails, it creates T-e with two components. If T-e reconnected with ε∈E(G)\\E(T) and form T_(ε\\e)=T+ε-e such that W_(α,β) (T_(ε\\e)) is minimum, then ε is a best swap edge (BSE) of e w.r.t W_( α,β). We devise an algorithm that finds a BSE ε∈E(G)\\E(T) w.r.t W_( α,β) for each e∈E(T) and computes W_( α,β) (T_(ε\\e) ). We call the algorithm &quot;all best swap edges w.r.t. W_( α,β)&quot;(ABSEW). Preprocessing for ABSEW takes O(n)-time, whereas solving ABSEW has an average time-complexity of O((m-n)log n) and a best time-complexity of O(m-n), all in O(m)-space, where (m,n)=(|E(G)|,|V(G)|). For dense graphs, however, the average time reaches O(m-n). T&#x27;s routing cost (RC) for a given set of sources S⊆ V(G) equals ∑_((a,b)∈V(T)×S )d_T (u,v). For 2-edge-connected positively edge-weighted graphs and some specified |S|, researchers have found a BSE for each edge of an ST w.r.t. RC. The solutions have time complexities of O(m2^O(α(2m,2m)) .log^2 n) (|S|=O(1) or n), O(m.log n+n^2 ) (|S|=2), and O(mn) (|S|&gt;2) for the specified |S|&#x27;s. Our algorithm outperforms existing algorithms regarding RC with no limit on |S|, edge and vertex weights, or graph type, while also computing the RC for each BSE. Assume T is a positively weighted n-vertex tree, and e∈ E(T) fails. If we reconnect the components of T-e with ε∈E(T^c) such that, W_( α,β) (T_(ε\\e) ) is minimum, then ε is called a best switch (BS) of e w.r.t. W_(α,β). For the inputs e∈ E(T) and w,α,β ∈R^+, we find ε, T_(ε\\e), and W_(α,β) (T_(ε\\e) ) with the worst average time of O(log⁡〖n)〗 and the best average time of O(1) where ε is a BS of e w.r.t. W_(α,β) and the weight of ε is w. There are comparable algorithms to ours only w.r.t W_( 1,0) or W_( 0,1) which are relatively complicated and limited. In our algorithm α,β can be changed at any step without affecting complexities or preprocessing.A subgraph H of a simple graph G is isomeric if d_G (u,v)=d_H (u,v), ∀u,v∈V(H). And G is distance-preserving if it has at least a k-vertex isometric subgraph for each k, 1≤k≤|V(G)|. There is a relatively old conjecture by Nussbaum and Esfahanian that says: if deg_G (v)&gt;n/2, ∀v∈V(G), then G is distance-preserving. We will have a close asymptotic approach to the conjecture.One added edge to a simple graph G (w_G=1) is called inset edge and mutates G. Establishing some regular and extensive matrix tools, we devised an algorithm that computes and sorts the gradient of the inset edges of a tree regarding the total distance, D(G)=∑_({u,v}⊆V(G))d_G (u,v) for G. The algorithms&#x27; average time complexity is minimal, reducing the previous algorithm from O(n^5) to an average of n^2 O(log⁡n), where n=|V(G)|. Indeed, we compute the total distance of O(n^2) unicyclic graphs each on average of O(log⁡n)-time and the best time of O(1).","abstract_has_math":false,"creators":["Khalifeh, Mohammad Hosein"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Esfahanian, Abdol-Hossein","Sagan, Bruce E","Kulkarni, Sandeep","Torng, Eric"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023","date_published":"2023","updated_at":"2026-11-18T18:57:56Z","subjects":["Computer engineering","Computer science","Mathematics"],"languages":["English"],"rights":["Attribution 4.0 International"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:51183","isbn:9798379589769","oclc:on1396767539","oclc:1396767539","umi:30486895","local:Khalifeh_grad.msu_0128D_19759"],"render_values":[{"text":"etd:51183","href":null,"code":true},{"text":"isbn:9798379589769","href":null,"code":true},{"text":"oclc:on1396767539","href":null,"code":true},{"text":"oclc:1396767539","href":null,"code":true},{"text":"umi:30486895","href":null,"code":true},{"text":"local:Khalifeh_grad.msu_0128D_19759","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://doi.org/doi:10.25335/vyd3-3e91","outbound_label":"DOI","outbound_source":"dc:identifier","record_url":"https://doi.org/doi:10.25335/vyd3-3e91","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_51183","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Esfahanian, Abdol-Hossein","Sagan, Bruce E","Kulkarni, Sandeep","Torng, Eric"]},{"key":"dc:creator","label":"Author","values":["Khalifeh, Mohammad Hosein"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023"]},{"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":["Computer engineering","Computer science","Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution 4.0 International"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:51183","isbn:9798379589769","oclc:on1396767539","oclc:1396767539","umi:30486895","local:Khalifeh_grad.msu_0128D_19759","https://doi.org/doi:10.25335/vyd3-3e91"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Most networks constantly change, and predicting links or recovering from link failures is crucial for maintaining a network. Distance-based graph invariants are important criteria for network maintenance. A graph mutation is a change in the edge set of a graph, and a graph gradient is the change in a graph invariant after a mutation. We present the general concepts of discrete integral and derivative for vertex and edge weighted graphs as a tool. Using the concepts, some related problems are solved more efficiently, flexibly, and simpler than the existing solutions.Let G=(V(G), E(G)) be a graph with vertex weight function f_G and edge weight function w_G. And d_G (u,v) denotes the distance of u,v∈V(G), the minimum sum of edge weights across all the paths connecting u and v. Then assumeW_(α,β) (G)=∑_({u,v}⊆V(G))[αf_G⁡(u) ×f_G(v)+β(f_G⁡(u) +f_G⁡(v)) ] d_G (u,v) , α,β∈R, and T is a spanning tree (ST) of G. If an edge e∈E(T) fails, it creates T-e with two components. If T-e reconnected with ε∈E(G)\\E(T) and form T_(ε\\e)=T+ε-e such that W_(α,β) (T_(ε\\e)) is minimum, then ε is a best swap edge (BSE) of e w.r.t W_( α,β). We devise an algorithm that finds a BSE ε∈E(G)\\E(T) w.r.t W_( α,β) for each e∈E(T) and computes W_( α,β) (T_(ε\\e) ). We call the algorithm \"all best swap edges w.r.t. W_( α,β)\"(ABSEW). Preprocessing for ABSEW takes O(n)-time, whereas solving ABSEW has an average time-complexity of O((m-n)log n) and a best time-complexity of O(m-n), all in O(m)-space, where (m,n)=(|E(G)|,|V(G)|). For dense graphs, however, the average time reaches O(m-n). T's routing cost (RC) for a given set of sources S⊆ V(G) equals ∑_((a,b)∈V(T)×S )d_T (u,v). For 2-edge-connected positively edge-weighted graphs and some specified |S|, researchers have found a BSE for each edge of an ST w.r.t. RC. The solutions have time complexities of O(m2^O(α(2m,2m)) .log^2 n) (|S|=O(1) or n), O(m.log n+n^2 ) (|S|=2), and O(mn) (|S|>2) for the specified |S|'s. Our algorithm outperforms existing algorithms regarding RC with no limit on |S|, edge and vertex weights, or graph type, while also computing the RC for each BSE. Assume T is a positively weighted n-vertex tree, and e∈ E(T) fails. If we reconnect the components of T-e with ε∈E(T^c) such that, W_( α,β) (T_(ε\\e) ) is minimum, then ε is called a best switch (BS) of e w.r.t. W_(α,β). For the inputs e∈ E(T) and w,α,β ∈R^+, we find ε, T_(ε\\e), and W_(α,β) (T_(ε\\e) ) with the worst average time of O(log⁡〖n)〗 and the best average time of O(1) where ε is a BS of e w.r.t. W_(α,β) and the weight of ε is w. There are comparable algorithms to ours only w.r.t W_( 1,0) or W_( 0,1) which are relatively complicated and limited. In our algorithm α,β can be changed at any step without affecting complexities or preprocessing.A subgraph H of a simple graph G is isomeric if d_G (u,v)=d_H (u,v), ∀u,v∈V(H). And G is distance-preserving if it has at least a k-vertex isometric subgraph for each k, 1≤k≤|V(G)|. There is a relatively old conjecture by Nussbaum and Esfahanian that says: if deg_G (v)>n/2, ∀v∈V(G), then G is distance-preserving. We will have a close asymptotic approach to the conjecture.One added edge to a simple graph G (w_G=1) is called inset edge and mutates G. Establishing some regular and extensive matrix tools, we devised an algorithm that computes and sorts the gradient of the inset edges of a tree regarding the total distance, D(G)=∑_({u,v}⊆V(G))d_G (u,v) for G. The algorithms' average time complexity is minimal, reducing the previous algorithm from O(n^5) to an average of n^2 O(log⁡n), where n=|V(G)|. Indeed, we compute the total distance of O(n^2) unicyclic graphs each on average of O(log⁡n)-time and the best time of O(1).","Thesis (Ph. D.)--Michigan State University. Computer Science, 2023","Includes bibliographical references"]},{"key":"dc:format","label":"Dc Format","values":["125 pages","application/pdf"]},{"key":"dc:title","label":"Title","values":["Graph mutation, graph distance, and graph gradient"]}]}],"canonical_facts":{"dc:contributor":["Esfahanian, Abdol-Hossein","Sagan, Bruce E","Kulkarni, Sandeep","Torng, Eric"],"dc:creator":["Khalifeh, Mohammad Hosein"],"dc:date":["2023"],"dc:description":["Most networks constantly change, and predicting links or recovering from link failures is crucial for maintaining a network. Distance-based graph invariants are important criteria for network maintenance. A graph mutation is a change in the edge set of a graph, and a graph gradient is the change in a graph invariant after a mutation. We present the general concepts of discrete integral and derivative for vertex and edge weighted graphs as a tool. Using the concepts, some related problems are solved more efficiently, flexibly, and simpler than the existing solutions.Let G=(V(G), E(G)) be a graph with vertex weight function f_G and edge weight function w_G. And d_G (u,v) denotes the distance of u,v∈V(G), the minimum sum of edge weights across all the paths connecting u and v. Then assumeW_(α,β) (G)=∑_({u,v}⊆V(G))[αf_G⁡(u) ×f_G(v)+β(f_G⁡(u) +f_G⁡(v)) ] d_G (u,v) , α,β∈R, and T is a spanning tree (ST) of G. If an edge e∈E(T) fails, it creates T-e with two components. If T-e reconnected with ε∈E(G)\\E(T) and form T_(ε\\e)=T+ε-e such that W_(α,β) (T_(ε\\e)) is minimum, then ε is a best swap edge (BSE) of e w.r.t W_( α,β). We devise an algorithm that finds a BSE ε∈E(G)\\E(T) w.r.t W_( α,β) for each e∈E(T) and computes W_( α,β) (T_(ε\\e) ). We call the algorithm \"all best swap edges w.r.t. W_( α,β)\"(ABSEW). Preprocessing for ABSEW takes O(n)-time, whereas solving ABSEW has an average time-complexity of O((m-n)log n) and a best time-complexity of O(m-n), all in O(m)-space, where (m,n)=(|E(G)|,|V(G)|). For dense graphs, however, the average time reaches O(m-n). T's routing cost (RC) for a given set of sources S⊆ V(G) equals ∑_((a,b)∈V(T)×S )d_T (u,v). For 2-edge-connected positively edge-weighted graphs and some specified |S|, researchers have found a BSE for each edge of an ST w.r.t. RC. The solutions have time complexities of O(m2^O(α(2m,2m)) .log^2 n) (|S|=O(1) or n), O(m.log n+n^2 ) (|S|=2), and O(mn) (|S|>2) for the specified |S|'s. Our algorithm outperforms existing algorithms regarding RC with no limit on |S|, edge and vertex weights, or graph type, while also computing the RC for each BSE. Assume T is a positively weighted n-vertex tree, and e∈ E(T) fails. If we reconnect the components of T-e with ε∈E(T^c) such that, W_( α,β) (T_(ε\\e) ) is minimum, then ε is called a best switch (BS) of e w.r.t. W_(α,β). For the inputs e∈ E(T) and w,α,β ∈R^+, we find ε, T_(ε\\e), and W_(α,β) (T_(ε\\e) ) with the worst average time of O(log⁡〖n)〗 and the best average time of O(1) where ε is a BS of e w.r.t. W_(α,β) and the weight of ε is w. There are comparable algorithms to ours only w.r.t W_( 1,0) or W_( 0,1) which are relatively complicated and limited. In our algorithm α,β can be changed at any step without affecting complexities or preprocessing.A subgraph H of a simple graph G is isomeric if d_G (u,v)=d_H (u,v), ∀u,v∈V(H). And G is distance-preserving if it has at least a k-vertex isometric subgraph for each k, 1≤k≤|V(G)|. There is a relatively old conjecture by Nussbaum and Esfahanian that says: if deg_G (v)>n/2, ∀v∈V(G), then G is distance-preserving. We will have a close asymptotic approach to the conjecture.One added edge to a simple graph G (w_G=1) is called inset edge and mutates G. Establishing some regular and extensive matrix tools, we devised an algorithm that computes and sorts the gradient of the inset edges of a tree regarding the total distance, D(G)=∑_({u,v}⊆V(G))d_G (u,v) for G. The algorithms' average time complexity is minimal, reducing the previous algorithm from O(n^5) to an average of n^2 O(log⁡n), where n=|V(G)|. Indeed, we compute the total distance of O(n^2) unicyclic graphs each on average of O(log⁡n)-time and the best time of O(1).","Thesis (Ph. D.)--Michigan State University. Computer Science, 2023","Includes bibliographical references"],"dc:format":["125 pages","application/pdf"],"dc:identifier":["etd:51183","isbn:9798379589769","oclc:on1396767539","oclc:1396767539","umi:30486895","local:Khalifeh_grad.msu_0128D_19759","https://doi.org/doi:10.25335/vyd3-3e91"],"dc:language":["English"],"dc:relation":["Electronic Theses & Dissertations"],"dc:rights":["Attribution 4.0 International"],"dc:subject":["Computer engineering","Computer science","Mathematics"],"dc:title":["Graph mutation, graph distance, and graph gradient"],"dc:type":["Text","Theses"]},"updated_at":"2026-11-18T18:57:56Z"}