國立虎尾科技大學 |

Graph Mutation, Graph Distance, and Graph Gradient.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Graph Mutation, Graph Distance, and Graph Gradient./
Author:	Khalifeh, Mohammad Hosein.
Description:	1 online resource (125 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 84-11, Section: B.
Contained By:	Dissertations Abstracts International84-11B.
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9798379589769

Graph Mutation, Graph Distance, and Graph Gradient.
Khalifeh, Mohammad Hosein.

Graph Mutation, Graph Distance, and Graph Gradient. - 1 online resource (125 pages)

Source: Dissertations Abstracts International, Volume: 84-11, Section: B.

Thesis (Ph.D.)--Michigan State University, 2023.

Includes bibliographical references

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 �� and edge weight function ��.And ��(��,��)denotes the distance of ��,��∈��(��), the minimum sum of edge weights across all the paths connecting �� and ��. Then assume. ��,��(G)=∑[��(��)×��(��)+��(��(��)+��(��))]��(��,��){��,��}⊆��(��), ��,��∈ℝ,and ��is a spanning tree(ST) of ��. If an edge��∈��(��)fails,it creates��−��withtwo components. If ��−��reconnected with ��∈��(��)\��(��)and form��\��=��+��−esuch that��,��(��\��)is minimum, then ��isa best swap edge (BSE) of ��w.r.t ��,��. We devise an algorithm that finds a BSE ��∈��(��)\��(��)w.r.t ��,��for each ��∈��(��)and computes ��,��(��\��). We call the algorithm “all best swap edges w.r.t.��,��”(ABSEW). Preprocessing for ABSEWtakes ��(��)-time, whereas solving ABSEW has an average time-complexity of ��((��−��)log��)and a best time-complexity of ��(��−��), all in ��(��)-space, where (��,��)=(|��(��)|,|��(��)|). For dense graphs, however, the average time reaches ��(��−��). ��’s routing cost(RC) for a given set of sources ��⊆��(��)equals ∑��(��,��)(��,��)∈��(��)×��. For 2-edge-connected positively edge-weighted graphs and some specified |��|, researchers have found a BSE for each edge of an ST w.r.t. RC. The solutions have time complexities of ��(��2��(��(2��,2��)).log2��)(|��|=��(1)or ��),��(��.log��+��2)(|��|=2),and��(��)(|��|>2)for the specified |��|’s. Our algorithm outperforms existing algorithms regarding RC with no limit on |��|, edge and vertex weights, or graph type, while also computing the RC for each BSE.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798379589769Subjects--Topical Terms:

573171
Computer science.
Subjects--Index Terms:

Discrete derivativeIndex Terms--Genre/Form:

554714
Electronic books.

Graph Mutation, Graph Distance, and Graph Gradient.
LDR:05707ntm a22004217 4500 001 1143590
005 20240517104606.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798379589769
035 $a (MiAaPQ)AAI30486895
035 $a AAI30486895
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Khalifeh, Mohammad Hosein. $3 1468323
245 1 0 $a Graph Mutation, Graph Distance, and Graph Gradient.
264 0 $c 2023
300 $a 1 online resource (125 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 84-11, Section: B.
500 $a Advisor: Esfahanian, Abdol-Hossein.
502 $a Thesis (Ph.D.)--Michigan State University, 2023.
504 $a Includes bibliographical references
520 $a 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 𝑓𝐺 and edge weight function 𝑤𝐺.And 𝑑𝐺(𝑢,𝑣)denotes the distance of 𝑢,𝑣∈𝑉(𝐺), the minimum sum of edge weights across all the paths connecting 𝑢 and 𝑣. Then assume. 𝑊𝛼,𝛽(G)=∑[𝛼𝑓𝐺(𝑢)×𝑓𝐺(𝑣)+𝛽(𝑓𝐺(𝑢)+𝑓𝐺(𝑣))]𝑑𝐺(𝑢,𝑣){𝑢,𝑣}⊆𝑉(𝐺), 𝛼,𝛽∈ℝ,and 𝑇is a spanning tree(ST) of 𝐺. If an edge𝑒∈𝐸(𝑇)fails,it creates𝑇−𝑒withtwo components. If 𝑇−𝑒reconnected with 𝜖∈𝐸(𝐺)\𝐸(𝑇)and form𝑇𝜖\𝑒=𝑇+𝜖−esuch that𝑊𝛼,𝛽(𝑇𝜖\𝑒)is minimum, then 𝜖isa best swap edge (BSE) of 𝑒w.r.t 𝑊𝛼,𝛽. We devise an algorithm that finds a BSE 𝜖∈𝐸(𝐺)\𝐸(𝑇)w.r.t 𝑊𝛼,𝛽for each 𝑒∈𝐸(𝑇)and computes 𝑊𝛼,𝛽(𝑇𝜖\𝑒). We call the algorithm “all best swap edges w.r.t.𝑊𝛼,𝛽”(ABSEW). Preprocessing for ABSEWtakes 𝑂(𝑛)-time, whereas solving ABSEW has an average time-complexity of 𝑂((𝑚−𝑛)log𝑛)and a best time-complexity of 𝑂(𝑚−𝑛), all in 𝑂(𝑚)-space, where (𝑚,𝑛)=(|𝐸(𝐺)|,|𝑉(𝐺)|). For dense graphs, however, the average time reaches 𝑂(𝑚−𝑛). 𝑇’s routing cost(RC) for a given set of sources 𝑆⊆𝑉(𝐺)equals ∑𝑑𝑇(𝑢,𝑣)(𝑎,𝑏)∈𝑉(𝑇)×𝑆. For 2-edge-connected positively edge-weighted graphs and some specified |𝑆|, researchers have found a BSE for each edge of an ST w.r.t. RC. The solutions have time complexities of 𝑂(𝑚2𝑂(𝛼(2𝑚,2𝑚)).log2𝑛)(|𝑆|=𝑂(1)or 𝑛),𝑂(𝑚.log𝑛+𝑛2)(|𝑆|=2),and𝑂(𝑚𝑛)(|𝑆|>2)for the specified |𝑆|’s. Our algorithm outperforms existing algorithms regarding RC with no limit on |𝑆|, edge and vertex weights, or graph type, while also computing the RC for each BSE.
520 $a Assume 𝑇is a positively weighted 𝑛-vertex tree, and 𝑒∈𝐸(𝑇)fails. If we reconnect the components of 𝑇−𝑒with 𝜖∈𝐸(𝑇𝑐)such that, 𝑊𝛼,𝛽(𝑇𝜖\𝑒)is minimum, then 𝜖is called a best switch(BS) of 𝑒w.r.t. 𝑊𝛼,𝛽. For the inputs 𝑒∈𝐸(𝑇)and 𝑤,𝛼,𝛽∈ℝ+, we find𝜖, 𝑇𝜖\𝑒, and 𝑊𝛼,𝛽(𝑇𝜖\𝑒)with the worst average time of 𝑂(log𝑛)and the best average time of 𝑂(1)where 𝜖is a BS of 𝑒w.r.t. 𝑊𝛼,𝛽and the weight of 𝜖is 𝑤. There are comparablealgorithms to ours only w.r.t 𝑊1,0or 𝑊0,1which are relatively complicatedand limited. In ouralgorithm𝛼,𝛽can be changed at any step without affectingcomplexitiesor preprocessing. A subgraph 𝐻of a simple graph 𝐺is isomericif 𝑑𝐺(𝑢,𝑣)=𝑑𝐻(𝑢,𝑣), ∀𝑢,𝑣∈𝑉(𝐻). And 𝐺is distance-preservingif it has at least a 𝑘-vertex isometricsubgraph for each 𝑘, 1≤𝑘≤|𝑉(𝐺)|.There isa relatively old conjectureby Nussbaum and Esfahanianthat says:if deg𝐺(𝑣)>𝑛2, ∀𝑣∈𝑉(𝐺), then G is distance-preserving. We will have acloseasymptotic approach to the conjecture. One added edge to a simple graph𝐺(𝑤𝐺=1)iscalled inset edgeandmutates 𝐺. Establishing some regularand extensivematrix tools, we devised an algorithm that computesand sortsthe gradientof the inset edgesof a treeregarding thetotal distance, 𝐷(𝐺)=∑𝑑𝐺(𝑢,𝑣){𝑢,𝑣}⊆𝑉(𝐺)for𝐺.The algorithms’ averagetime complexity is minimal,reducing the previousalgorithmfrom 𝑂(𝑛5)to an average of 𝑛2𝑂(log𝑛),where 𝑛=|𝑉(𝐺)|.Indeed, we compute the total distance of 𝑂(𝑛2)unicyclic graphseach on average of 𝑂(log𝑛)-time andthebest time of 𝑂(1).
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Mathematics. $3 527692
650 4 $a Computer engineering. $3 569006
653 $a Discrete derivative
653 $a Discrete integral
653 $a Graph gradient
653 $a Graph mutation
653 $a Spanning tree
653 $a Swap edge
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0405
690 $a 0464
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Michigan State University. $b Computer Science - Doctor of Philosophy. $3 1188138
773 0 $t Dissertations Abstracts International $g 84-11B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30486895 $z click for full text (PQDT)