To see the other types of publications on this topic, follow the link: Vertex's Neighbors.
Journal articles on the topic 'Vertex's Neighbors'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Vertex's Neighbors.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Gou, Yutong, Jianyang Gao, Yuexuan Xu, and Cheng Long. "SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search." Proceedings of the ACM on Management of Data 3, no. 1 (2025): 1–26. https://doi.org/10.1145/3709730.
Full textAbstract:
Approximate nearest neighbor (ANN) search in high-dimensional Euclidean space has a broad range of applications. Among existing ANN algorithms, graph-based methods have shown superior performance in terms of the time-accuracy trade-off. However, they face performance bottlenecks due to the random memory accesses caused by the searching process on the graph indices and the costs of computing exact distances to guide the searching process. To relieve the bottlenecks, a recent method named NGT-QG makes an attempt by integrating quantization and graph. It (1) replicates and stores the quantization codes of a vertex's neighbors compactly so that they can be accessed sequentially, and (2) uses a SIMD-based implementation named FastScan to efficiently estimate distances based on the quantization codes in batch for guiding the searching process. While NGT-QG achieves promising improvements over the vanilla graph-based methods, it has not fully unleashed the potential of integrating quantization and graph. For instance, it entails a re-ranking step to compute exact distances at the end, which introduces extra random memory accesses; its graph structure is not jointly designed considering the in-batch nature of FastScan, which causes wastes of computation in searching. In this work, following NGT-QG, we present a new method named SymphonyQG, which achieves more symphonious integration of quantization and graph (e.g., it avoids the explicit re-ranking step and refines the graph structure to be more aligned with FastScan). Based on extensive experiments on real-world datasets, SymphonyQG establishes the new state-of-the-art in terms of the time-accuracy trade-off: at 95% recall, SymphonyQG achieves 1.5x-4.5x QPS compared with the most competitive baselines and achieves 3.5x-17x QPS compared with the classical library HNSWlib across all tested datasets. At the same time, its indexing is at least 8x faster than NGT-QG.
2
Zhang, Chenghan, Yuanyuan Zhu, and Lijun Chang. "A Local Search Approach to Efficient ( k,p )-Core Maintenance." Proceedings of the ACM on Management of Data 3, no. 1 (2025): 1–26. https://doi.org/10.1145/3709654.
Full textAbstract:
The (( k,p ))-core model was recently proposed to capture engagement dynamics by considering both intra-community interactions (i.e., the k -core structure) and inter-community interactions (i.e., the p -fraction property). It is a refinement of the classic k -core, by introducing an extra parameter p to customize the engagement within a community at a finer granularity. In this paper, we study the problem of maintaining all (k,p)-cores (essentially, maintaining the p-numbers for all vertices) for dynamic graphs. The existing Global approach conducts a global peeling, almost from scratch, for all vertices whose old p-numbers are within a computed range [p - ,p + ], and thus is inefficient. We propose a new Local approach which conducts local searches starting from the two end-points of the newly inserted or deleted edge, and then iteratively expands the search frontier by including their neighbors. Our algorithm is designed based on several fundamental properties that we prove in this paper to characterize the necessary condition for a vertex's p-number to change. Compared to Global, our Local approach implicitly obtains the optimal affected p-number range [p - * ,p + * ] ⊆ [p - ,p + ], and further skips many vertices whose p-numbers are within this range. Experimental results show that Local is on average two orders of magnitude faster than Global.
3
Naqvi, Shabbar, Muhammad Salman, Muhammad Ehtisham, Muhammad Fazil, and Masood Ur Rehman. "On the neighbor-distinguishing in generalized Petersen graphs." AIMS Mathematics 6, no. 12 (2021): 13734–45. http://dx.doi.org/10.3934/math.2021797.
Full textAbstract:
<abstract><p>In a connected graph $ G $, two adjacent vertices are said to be neighbors of each other. A vertex $ v $ adjacently distinguishes a pair $ (x, y) $ of two neighbors in $ G $ if the number of edges in $ v $-$ x $ geodesic and the number of edges in $ v $-$ y $ geodesic differ by one. A set $ S $ of vertices of $ G $ is a neighbor-distinguishing set for $ G $ if every two neighbors in $ G $ are adjacently distinguished by some element of $ S $. In this paper, we consider two families of generalized Petersen graphs and distinguish every two neighbors in these graphs by investigating their minimum neighbor-distinguishing sets, which are of coordinately two.</p></abstract>
4
Wang, Yanling, and Shiying Wang. "The 3-Good-Neighbor Connectivity of Modified Bubble-Sort Graphs." Mathematical Problems in Engineering 2020 (October 28, 2020): 1–18. http://dx.doi.org/10.1155/2020/7845987.
Full textAbstract:
Let G = V G , E G be a connected graph. A subset F ⊆ V G is called a g -good-neighbor cut if G − F is disconnected and each vertex of G − F has at least g neighbors. The g -good-neighbor connectivity of G is the minimum cardinality of g -good-neighbor cuts. The n -dimensional modified bubble-sort graph MB n is a special Cayley graph. It has many good properties. In this paper, we prove that the 3-good-neighbor connectivity of MB n is 8 n − 24 for n ≥ 6 .
5
Kim, Kijung. "The Italian Domination Numbers of Some Products of Directed Cycles." Mathematics 8, no. 9 (2020): 1472. http://dx.doi.org/10.3390/math8091472.
Full textAbstract:
An Italian dominating function on a digraph D with vertex set V(D) is defined as a function f:V(D)→{0,1,2} such that every vertex v∈V(D) with f(v)=0 has at least two in-neighbors assigned 1 under f or one in-neighbor w with f(w)=2. In this article, we determine the exact values of the Italian domination numbers of some products of directed cycles.
6
GU, MEI-MEI, RONG-XIA HAO, and AI-MEI YU. "The 1-Good-Neighbor Conditional Diagnosability of Some Regular Graphs." Journal of Interconnection Networks 17, no. 03n04 (2017): 1741001. http://dx.doi.org/10.1142/s0219265917410018.
Full textAbstract:
The g-good-neighbor conditional diagnosability is the maximum number of faulty vertices a network can guarantee to identify, under the condition that every fault-free vertex has at least g fault-free neighbors. In this paper, we study the 1-good-neighbor conditional diagnosabilities of some general k-regular k-connected graphs G under the PMC model and the MM* model. The main result [Formula: see text] under some conditions is obtained, where l is the maximum number of common neighbors between any two adjacent vertices in G. Moreover, the following results are derived: [Formula: see text] for the hierarchical star networks, [Formula: see text] for the BC networks, [Formula: see text] for the alternating group graphs [Formula: see text].
7
Sheikholeslami, Seyed Mahmoud, Asghar Bodaghli, and Lutz Volkmann. "Twin signed Roman domination numbers in directed graphs." Tamkang Journal of Mathematics 47, no. 3 (2016): 357–71. http://dx.doi.org/10.5556/j.tkjm.47.2016.2035.
Full textAbstract:
Let $D$ be a finite simple digraph with vertex set $V(D)$ and arc set $A(D)$. A twin signed Roman dominating function (TSRDF) on the digraph $D$ is a function $f:V(D)\rightarrow\{-1,1,2\}$ satisfying the conditions that (i) $\sum_{x\in N^-[v]}f(x)\ge 1$ and $\sum_{x\in N^+[v]}f(x)\ge 1$ for each $v\in V(D)$, where $N^-[v]$ (resp. $N^+[v]$) consists of $v$ and all in-neighbors (resp. out-neighbors) of $v$, and (ii) every vertex $u$ for which $f(u)=-1$ has an in-neighbor $v$ and an out-neighbor $w$ for which $f(v)=f(w)=2$. The weight of an TSRDF $f$ is $\omega(f)=\sum_{v\in V(D)}f(v)$. The twin signed Roman domination number $\gamma_{sR}^*(D)$ of $D$ is the minimum weight of an TSRDF on $D$. In this paper, we initiate the study of twin signed Roman domination in digraphs and we present some sharp bounds on $\gamma_{sR}^*(D)$. In addition, we determine the twin signed Roman domination number of some classes of digraphs.
8
Amjadi, J., and M. Soroudi. "Twin signed total Roman domination numbers in digraphs." Asian-European Journal of Mathematics 11, no. 03 (2018): 1850034. http://dx.doi.org/10.1142/s1793557118500341.
Full textAbstract:
Let [Formula: see text] be a finite simple digraph with vertex set [Formula: see text] and arc set [Formula: see text]. A twin signed total Roman dominating function (TSTRDF) on the digraph [Formula: see text] is a function [Formula: see text] satisfying the conditions that (i) [Formula: see text] and [Formula: see text] for each [Formula: see text], where [Formula: see text] (respectively [Formula: see text]) consists of all in-neighbors (respectively out-neighbors) of [Formula: see text], and (ii) every vertex [Formula: see text] for which [Formula: see text] has an in-neighbor [Formula: see text] and an out-neighbor [Formula: see text] with [Formula: see text]. The weight of an TSTRDF [Formula: see text] is [Formula: see text]. The twin signed total Roman domination number [Formula: see text] of [Formula: see text] is the minimum weight of an TSTRDF on [Formula: see text]. In this paper, we initiate the study of twin signed total Roman domination in digraphs and we present some sharp bounds on [Formula: see text]. In addition, we determine the twin signed Roman domination number of some classes of digraphs.
9
Amjadi, Jafar, and Fatemeh Pourhosseini. "Signed double Roman domination numbers in digraphs." Annals of the University of Craiova - Mathematics and Computer Science Series 48, no. 1 (2021): 194–205. http://dx.doi.org/10.52846/ami.v48i1.1305.
Full textAbstract:
"Let $D=(V,A)$ be a finite simple digraph. A signed double Roman dominating function (SDRD-function) on the digraph $D$ is a function $f:V(D)\rightarrow\{-1,1,2, 3\}$ satisfying the following conditions: (i) $\sum_{x\in N^-[v]}f(x)\ge 1$ for each $v\in V(D)$, where $N^-[v]$ consist of $v$ and all in-neighbors of $v$, and (ii) if $f(v)=-1$, then the vertex $v$ must have at least two in-neighbors assigned 2 under $f$ or one in-neighbor assigned 3, while if $f(v)=1$, then the vertex $v$ must have at least one in-neighbor assigned 2 or 3. The weight of a SDRD-function $f$ is the value $\sum_{x\in V(D)}f(x)$. The signed double Roman domination number (SDRD-number) $\gamma_{sdR}(D)$ of a digraph $D$ is the minimum weight of a SDRD-function on $D$. In this paper we study the SDRD-number of digraphs, and we present lower and upper bounds for $\gamma_{sdR}(D)$ in terms of the order, maximum degree and chromatic number of a digraph. In addition, we determine the SDRD-number of some classes of digraphs."
10
Goebbels, Steffen, Frank Gurski, and Dominique Komander. "The knapsack problem with special neighbor constraints." Mathematical Methods of Operations Research 95, no. 1 (2021): 1–34. http://dx.doi.org/10.1007/s00186-021-00767-5.
Full textAbstract:
AbstractThe knapsack problem is one of the simplest and most fundamental NP-hard problems in combinatorial optimization. We consider two knapsack problems which contain additional constraints in the form of directed graphs whose vertex set corresponds to the item set. In the one-neighbor knapsack problem, an item can be chosen only if at least one of its neighbors is chosen. In the all-neighbors knapsack problem, an item can be chosen only if all its neighbors are chosen. For both problems, we consider uniform and general profits and weights. We prove upper bounds for the time complexity of these problems when restricting the graph constraints to special sets of digraphs. We discuss directed co-graphs, minimal series-parallel digraphs, and directed trees.
11
Jiang, Huiqin, Pu Wu, Zehui Shao, Yongsheng Rao, and Jia-Bao Liu. "The Double Roman Domination Numbers of Generalized Petersen Graphs P(n, 2)." Mathematics 6, no. 10 (2018): 206. http://dx.doi.org/10.3390/math6100206.
Full textAbstract:
A double Roman dominating function (DRDF) f on a given graph G is a mapping from V ( G ) to { 0 , 1 , 2 , 3 } in such a way that a vertex u for which f ( u ) = 0 has at least a neighbor labeled 3 or two neighbors both labeled 2 and a vertex u for which f ( u ) = 1 has at least a neighbor labeled 2 or 3. The weight of a DRDF f is the value w ( f ) = ∑ u ∈ V ( G ) f ( u ) . The minimum weight of a DRDF on a graph G is called the double Roman domination number γ d R ( G ) of G. In this paper, we determine the exact value of the double Roman domination number of the generalized Petersen graphs P ( n , 2 ) by using a discharging approach.
12
He, Yizhang, Kai Wang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. "Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy." Proceedings of the ACM on Management of Data 2, no. 6 (2024): 1–26. https://doi.org/10.1145/3698803.
Full textAbstract:
Bipartite graphs, formed by two vertex layers, arise as a natural fit for modeling the relationships between two groups of entities. In bipartite graphs, common neighborhood computation between two vertices on the same vertex layer is a basic operator, which is easily solvable in general settings. However, it inevitably involves releasing the neighborhood information of vertices, posing a significant privacy risk for users in real-world applications. To protect edge privacy in bipartite graphs, in this paper, we study the problem of estimating the number of common neighbors of two vertices on the same layer under edge local differential privacy (edge LDP). The problem is challenging in the context of edge LDP since each vertex on the opposite layer of the query vertices can potentially be a common neighbor. To obtain efficient and accurate estimates, we propose a multiple-round framework that significantly reduces the candidate pool of common neighbors and enables the query vertices to construct unbiased estimators locally. Furthermore, we improve data utility by incorporating the estimators built from the neighbors of both query vertices and devise privacy budget allocation optimizations. These improve the estimator's robustness and consistency, particularly against query vertices with imbalanced degrees. Extensive experiments on 15 datasets validate the effectiveness and efficiency of our proposed techniques.
13
Wang, Peng, Chenxiao Wu, Teng Huang, and Yizhang Chen. "A Supervised Link Prediction Method Using Optimized Vertex Collocation Profile." Entropy 24, no. 10 (2022): 1465. http://dx.doi.org/10.3390/e24101465.
Full textAbstract:
Classical link prediction methods mainly utilize vertex information and topological structure to predict missing links in networks. However, accessing vertex information in real-world networks, such as social networks, is still challenging. Moreover, link prediction methods based on topological structure are usually heuristic, and mainly consider common neighbors, vertex degrees and paths, which cannot fully represent the topology context. In recent years, network embedding models have shown efficiency for link prediction, but they lack interpretability. To address these issues, this paper proposes a novel link prediction method based on an optimized vertex collocation profile (OVCP). First, the 7-subgraph topology was proposed to represent the topology context of vertexes. Second, any 7-subgraph can be converted into a unique address by OVCP, and then we obtained the interpretable feature vectors of vertexes. Third, the classification model with OVCP features was used to predict links, and the overlapping community detection algorithm was employed to divide a network into multiple small communities, which can greatly reduce the complexity of our method. Experimental results demonstrate that the proposed method can achieve a promising performance compared with traditional link prediction methods, and has better interpretability than network-embedding-based methods.
14
Shahbazi, L., H. Abdollahzadeh Ahangar, R. Khoeilar, and S. M. Sheikholeslami. "Signed total double Roman k-domination in graphs." Discrete Mathematics, Algorithms and Applications 12, no. 01 (2019): 2050009. http://dx.doi.org/10.1142/s1793830920500093.
Full textAbstract:
A signed total double Roman [Formula: see text]-dominating function (STDRkDF) on an isolated-free graph [Formula: see text] is a function [Formula: see text] such that (i) every vertex [Formula: see text] with [Formula: see text] has at least two neighbors assigned 2 under [Formula: see text] or at least one neighbor [Formula: see text] with [Formula: see text], (ii) every vertex [Formula: see text] with [Formula: see text] has at least one neighbor [Formula: see text] with [Formula: see text] and (iii) [Formula: see text] holds for any vertex [Formula: see text]. The weight of an STDRkDF is the value [Formula: see text] The signed total double Roman [Formula: see text]-domination number [Formula: see text] is the minimum weight among all STDRkDFs on [Formula: see text]. In this paper, we initiate the study of the signed total double Roman [Formula: see text]-domination in graphs and present some sharp bounds for this parameter. In addition, we determine the signed total double Roman [Formula: see text]-domination of paths for [Formula: see text].
15
Sheikholeslami, Seyed Mahmoud, and Lutz Volkmann. "Twin signed Roman domatic numbers in digraphs." Tamkang Journal of Mathematics 48, no. 3 (2017): 265–72. http://dx.doi.org/10.5556/j.tkjm.48.2017.2306.
Full textAbstract:
Let $D$ be a finite simple digraph with vertex set $V(D)$. A twin signed Roman dominating function on the digraph $D$ is a function $f:V(D)\rightarrow\{-1,1,2\}$ satisfying the conditions that (i) $\sum_{x\in N^-[v]}f(x)\ge 1$ and $\sum_{x\in N^+[v]}f(x)\ge 1$ for each $v\in V(D)$, where $N^-[v]$ (resp. $N^+[v]$) consists of $v$ and all in-neighbors (resp. out-neighbors) of $v$, and (ii) every vertex $u$ for which $f(u)=-1$ has an in-neighbor $v$ and an out-neighbor $w$ for which $f(v)=f(w)=2$. A set $\{f_1,f_2,\ldots,f_d\}$ of distinct twin signed Roman dominating functions on $D$ with the property that $\sum_{i=1}^df_i(v)\le 1$ for each $v\in V(D)$, is called a twin signed Roman dominating family (of functions) on $D$. The maximum number of functions in a twin signed Roman dominating family on $D$ is the twin signed Roman domatic number of $D$, denoted by $d_{sR}^*(D)$. In this paper, we initiate the study of the twin signed Roman domatic number in digraphs and we present some sharp bounds on $d_{sR}^*(D)$. In addition, we determine the twin signed Roman domatic number of some classes of digraphs.
16
Nagy, Zoltán Lóránt. "Partitioning the projective plane into two incidence‐rich parts." Journal of Combinatorial Designs 32, no. 12 (2024): 703–14. http://dx.doi.org/10.1002/jcd.21956.
Full textAbstract:
AbstractAn internal or friendly partition of a vertex set of a graph is a partition to two nonempty sets such that every vertex has at least as many neighbours in its own class as in the other one. Motivated by Diwan's existence proof on internal partitions of graphs with high girth, we give constructive proofs for the existence of internal partitions in the incidence graph of projective planes and discuss its geometric properties. In addition, we determine exactly the maximum possible difference between the sizes of the neighbour set in its own class and the neighbour set of the other class that can be attained for all vertices at the same time for the incidence graphs of Desarguesian planes of square order.
17
Gao, Hong, Xing Liu, Yuanyuan Guo, and Yuansheng Yang. "On Two Outer Independent Roman Domination Related Parameters in Torus Graphs." Mathematics 10, no. 18 (2022): 3361. http://dx.doi.org/10.3390/math10183361.
Full textAbstract:
In a graph G=(V,E), where every vertex is assigned 0, 1 or 2, f is an assignment such that every vertex assigned 0 has at least one neighbor assigned 2 and all vertices labeled by 0 are independent, then f is called an outer independent Roman dominating function (OIRDF). The domination is strengthened if every vertex is assigned 0, 1, 2 or 3, f is such an assignment that each vertex assigned 0 has at least two neighbors assigned 2 or one neighbor assigned 3, each vertex assigned 1 has at least one neighbor assigned 2 or 3, and all vertices labeled by 0 are independent, then f is called an outer independent double Roman dominating function (OIDRDF). The weight of an (OIDRDF) OIRDF f is the sum of f(v) for all v∈V. The outer independent (double) Roman domination number (γoidR(G)) γoiR(G) is the minimum weight taken over all (OIDRDFs) OIRDFs of G. In this article, we investigate these two parameters γoiR(G) and γoidR(G) of regular graphs and present lower bounds on them. We improve the lower bound on γoiR(G) for a regular graph presented by Ahangar et al. (2017). Furthermore, we present upper bounds on γoiR(G) and γoidR(G) for torus graphs. Furthermore, we determine the exact values of γoiR(C3□Cn) and γoiR(Cm□Cn) for m≡0(mod4) and n≡0(mod4), and the exact value of γoidR(C3□Cn). By our result, γoidR(Cm□Cn)≤5mn/4 which verifies the open question is correct for Cm□Cn that was presented by Ahangar et al. (2020).
18
Song, Jiaqi, Xingqin Qi, and Zhulou Cao. "An Independent Cascade Model of Graph Burning." Symmetry 15, no. 8 (2023): 1527. http://dx.doi.org/10.3390/sym15081527.
Full textAbstract:
Graph burning was introduced to simulate the spreading of news/information/rumors in social networks. The symmetric undirected graph is considered here. That is, vertex u can spread the information to vertex v, and symmetrically vertex v can also spread information to vertex u. When it is modeled as a graph burning process, a vertex can be set on fire directly or burned by its neighbor. Thus, the task is to find the minimum sequence of vertices chosen as sources of fire to burn the entire graph. This problem has been proved to be NP-hard. In this paper, from a new perspective, we introduce a generalized model called the Independent Cascade Graph Burning model, where a vertex v can be burned by one of its burning neighbors u only if the influence that u gives to v is larger than a given threshold β≥0. We determine the graph burning number with this new Independent Cascade Graph Burning model for several graphs and operation graphs and also discuss its upper and lower bounds.
19
Roberts, Matthew I. "Cover time for branching random walks on regular trees." Journal of Applied Probability 59, no. 1 (2022): 256–77. http://dx.doi.org/10.1017/jpr.2021.46.
Full textAbstract:
AbstractLet T be the regular tree in which every vertex has exactly $d\ge 3$ neighbours. Run a branching random walk on T, in which at each time step every particle gives birth to a random number of children with mean d and finite variance, and each of these children moves independently to a uniformly chosen neighbour of its parent. We show that, starting with one particle at some vertex 0 and conditionally on survival of the process, the time it takes for every vertex within distance r of 0 to be hit by a particle of the branching random walk is $r + ({2}/{\log(3/2)})\log\log r + {\mathrm{o}}(\log\log r)$ .
20
Krishnakumari, B., and Y. B. Venkatakrishnan. "Double domination and super domination in trees." Discrete Mathematics, Algorithms and Applications 08, no. 04 (2016): 1650067. http://dx.doi.org/10.1142/s1793830916500671.
Full textAbstract:
A vertex of a graph [Formula: see text] is said to dominate itself and all its neighbors. A double dominating set (DDS) of a graph [Formula: see text] is a set [Formula: see text] of vertices such that every vertex of [Formula: see text] is dominated by at least two vertices of [Formula: see text]. The double domination number of a graph [Formula: see text] is the minimum cardinality of a DDS of [Formula: see text]. For a graph [Formula: see text], a subset [Formula: see text] of [Formula: see text] is a super dominating set SDS if for every vertex of [Formula: see text] there exists an external private neighbor of [Formula: see text] with respect to [Formula: see text]. The super domination number of [Formula: see text] is the minimum cardinality of a SDS of [Formula: see text]. We prove that for every tree [Formula: see text], [Formula: see text], and we characterize the trees attaining this bound.
21
Alhevaz, Abdollah, Mahsa Darkooti, Hadi Rahbani, and Yilun Shang. "Strong Equality of Perfect Roman and Weak Roman Domination in Trees." Mathematics 7, no. 10 (2019): 997. http://dx.doi.org/10.3390/math7100997.
Full textAbstract:
Let G = ( V , E ) be a graph and f : V ⟶ { 0 , 1 , 2 } be a function. Given a vertex u with f ( u ) = 0 , if all neighbors of u have zero weights, then u is called undefended with respect to f. Furthermore, if every vertex u with f ( u ) = 0 has a neighbor v with f ( v ) > 0 and the function f ′ : V ⟶ { 0 , 1 , 2 } with f ′ ( u ) = 1 , f ′ ( v ) = f ( v ) − 1 , f ′ ( w ) = f ( w ) if w ∈ V ∖ { u , v } has no undefended vertex, then f is called a weak Roman dominating function. Also, the function f is a perfect Roman dominating function if every vertex u with f ( u ) = 0 is adjacent to exactly one vertex v for which f ( v ) = 2 . Let the weight of f be w ( f ) = ∑ v ∈ V f ( v ) . The weak (resp., perfect) Roman domination number, denoted by γ r ( G ) (resp., γ R p ( G ) ), is the minimum weight of the weak (resp., perfect) Roman dominating function in G. In this paper, we characterize those trees where the perfect Roman domination number strongly equals the weak Roman domination number, in the sense that each weak Roman dominating function of minimum weight is, at the same time, perfect Roman dominating.
22
HEDETNIEMI, SANDRA M., STEPHEN T. HEDETNIEMI, K. E. KENNEDY, and ALICE A. McRAE. "SELF-STABILIZING ALGORITHMS FOR UNFRIENDLY PARTITIONS INTO TWO DISJOINT DOMINATING SETS." Parallel Processing Letters 23, no. 01 (2013): 1350001. http://dx.doi.org/10.1142/s0129626413500011.
Full textAbstract:
An unfriendly partition is a partition of the vertices of a graph G = (V,E) into two sets, say Red R(V) and Blue B(V), such that every Red vertex has at least as many Blue neighbors as Red neighbors, and every Blue vertex has at least as many Red neighbors as Blue neighbors. We present three polynomial time, self-stabilizing algorithms for finding unfriendly partitions in arbitrary graphs G, or equivalently into two disjoint dominating sets.
23
Miao, Fang, Wenjie Fan, Mustapha Chellali, Rana Khoeilar, Seyed Mahmoud Sheikholeslami, and Marzieh Soroudi. "On Two Open Problems on Double Vertex-Edge Domination in Graphs." Mathematics 7, no. 11 (2019): 1010. http://dx.doi.org/10.3390/math7111010.
Full textAbstract:
A vertex v of a graph G = ( V , E ) , ve-dominates every edge incident to v, as well as every edge adjacent to these incident edges. A set S ⊆ V is a double vertex-edge dominating set if every edge of E is ve-dominated by at least two vertices of S. The double vertex-edge domination number γ d v e ( G ) is the minimum cardinality of a double vertex-edge dominating set in G. A subset S ⊆ V is a total dominating set (respectively, a 2-dominating set) if every vertex in V has a neighbor in S (respectively, every vertex in V - S has at least two neighbors in S). The total domination number γ t ( G ) is the minimum cardinality of a total dominating set of G, and the 2-domination number γ 2 ( G ) is the minimum cardinality of a 2-dominating set of G . Krishnakumari et al. (2017) showed that for every triangle-free graph G , γ d v e ( G ) ≤ γ 2 ( G ) , and in addition, if G has no isolated vertices, then γ d v e ( G ) ≤ γ t ( G ) . Moreover, they posed the problem of characterizing those graphs attaining the equality in the previous bounds. In this paper, we characterize all trees T with γ d v e ( T ) = γ t ( T ) or γ d v e ( T ) = γ 2 ( T ) .
24
Hamja, Jamil, Seyed Mahmoud Sheikholeslami, Mina Esmaeeli, Cris L. Armada, and Imelda S. Aniversario. "Independent Double Roman Domination Stability in Graph." European Journal of Pure and Applied Mathematics 18, no. 2 (2025): 5984. https://doi.org/10.29020/nybg.ejpam.v18i2.5984.
Full textAbstract:
An independent double Roman dominating function (IDRD-function) on a graph $G$ is a function $f :V(G)\to \{0, 1, 2, 3\}$ having the property that (i) if $f(v) = 0$, then the vertex $v$ must have at least two neighbors assigned 2 under $f$ or one neighbor $w$ with $f(w) = 3$, and if $f(v) = 1$, then the vertex $v$ must have at least one neighbor $w$ with $f(w) \ge2$, and (ii) the subgraph induced by the vertices with positive weight under $f$ is edgeless. The weight of an IDRD-function is the sum of its function values over all vertices, and the independent double Roman domination number (IDRD-number) $i_{dR}(G)$ is the minimum weight of an IDRD-function on $G$. The $i_{dR}$-stability ($i^-_{dR}$-stability, $i^+_{dR}$-stability) of $G$, denoted by ${\rm st}_{i_{dR}}(G)$ (${\rm st}^-_{i_{dR}}(G)$, ${\rm st}^+_{i_{dR}}(G)$), is defined as the minimum size of a set of vertices whose removal changes (decreases, increases) the independent double Roman domination number. In this paper, we first determine the exact values on the $i_{dR}$-stability of some special classes of graphs, and then present some bounds on ${\rm st}_{i_{dR}}(G)$. In addition, for a tree $T$ with maximum degree $\Delta$, we show that ${\rm st}_{i_{dR}}(T)=1$ and ${\rm st}^-_{i_{dR}}(T)\le \Delta$, and characterize the trees that achieve the upper bound.
25
CHEN, JIN, FEI GAO, ANBO LE, LIFENG XI, and SHUHUA YIN. "A SMALL-WORLD AND SCALE-FREE NETWORK GENERATED BY SIERPINSKI TETRAHEDRON." Fractals 24, no. 01 (2016): 1650001. http://dx.doi.org/10.1142/s0218348x16500018.
Full textAbstract:
The Sierpinski tetrahedron is used to construct evolving networks, whose vertexes are all solid regular tetrahedra in the construction of the Sierpinski tetrahedron up to the stage [Formula: see text] and any two vertexes are neighbors if and only if the corresponding tetrahedra are in contact with each other on boundary. We show that such networks have the small-world and scale-free effects, but are not fractal scaling.
26
Chen, Meijia, Fahong Yu, and Dongping Zhu. "Community Partitioning Based on Coupling Density With Asymmetric Similarity Between Vertexes." International Journal of Cognitive Informatics and Natural Intelligence 19, no. 1 (2025): 1–20. https://doi.org/10.4018/ijcini.375349.
Full textAbstract:
Community partitioning has become an important approach for uncovering underlying patterns in complex network analysis. This paper proposes a coupling density model with asymmetric similarity between vertices, which considers weighted coupling relations between connected groups and vertex similarities to guide the generation of new partitions and to measure inter-community similarity. Directed similarity, as a promising quality criterion, captures the directional tendency from one vertex to another by incorporating local attributes such as degree, neighbors, co-neighbors, and their interrelations. Theoretical and empirical evaluations on both real-world and synthetic networks demonstrate that the proposed metric model outperforms traditional modularity and standard density measures. Furthermore, the model was effectively applied to analyze textile-related trade networks.
27
Wei, Zongtian, Yong Liu, and Anchan Mai. "Vertex-Neighbor-Scattering Number Of Trees." Advances in Pure Mathematics 01, no. 04 (2011): 160–62. http://dx.doi.org/10.4236/apm.2011.14029.
Full text
28
Zhuo, Youwei, Jingji Chen, Gengyu Rao, et al. "Distributed Graph Processing System and Processing-in-memory Architecture with Precise Loop-carried Dependency Guarantee." ACM Transactions on Computer Systems 37, no. 1-4 (2021): 1–37. http://dx.doi.org/10.1145/3453681.
Full textAbstract:
To hide the complexity of the underlying system, graph processing frameworks ask programmers to specify graph computations in user-defined functions (UDFs) of graph-oriented programming model. Due to the nature of distributed execution, current frameworks cannot precisely enforce the semantics of UDFs, leading to unnecessary computation and communication. It exemplifies a gap between programming model and runtime execution. This article proposes novel graph processing frameworks for distributed system and Processing-in-memory (PIM) architecture that precisely enforces loop-carried dependency; i.e., when a condition is satisfied by a neighbor, all following neighbors can be skipped. Our approach instruments the UDFs to express the loop-carried dependency, then the distributed execution framework enforces the precise semantics by performing dependency propagation dynamically. Enforcing loop-carried dependency requires the sequential processing of the neighbors of each vertex distributed in different nodes. We propose to circulant scheduling in the framework to allow different nodes to process disjoint sets of edges/vertices in parallel while satisfying the sequential requirement. The technique achieves an excellent trade-off between precise semantics and parallelism—the benefits of eliminating unnecessary computation and communication offset the reduced parallelism. We implement a new distributed graph processing framework SympleGraph, and two variants of runtime systems— GraphS and GraphSR —for PIM-based graph processing architecture, which significantly outperform the state-of-the-art.
29
Li, Wentao, Maolin Cai, Min Gao, Dong Wen, Lu Qin, and Wei Wang. "Expanding Reverse Nearest Neighbors." Proceedings of the VLDB Endowment 17, no. 4 (2023): 630–42. http://dx.doi.org/10.14778/3636218.3636220.
Full textAbstract:
In a graph, the reverse nearest neighbors (RNN) of vertex f refer to the set of vertices that consider f as their nearest neighbor. When f represents a facility like a subway station, its RNN comprises potential users who prefer the nearest facility. In practice, there may be underutilized facilities with small RNN sizes, and relocating these facilities to expand their service can be costly or infeasible. A more cost-effective approach involves selectively upgrading some edges (e.g., reducing their weights) to expand the RNN sizes of underutilized facilities. This motivates our research on the Expanding Reverse Nearest Neighbors (ERNN) problem, which aims to maximize the RNN size of a target facility by upgrading a limited number of edges. Solving the ERNN problem allows underutilized facilities to serve more users and alleviate the burden on other facilities. Despite numerous potential applications, ERNN is hard to solve: It can be proven to be NP-hard and APX-hard, and it exhibits non-monotonic and non-submodular properties. To overcome these challenges, we propose novel greedy algorithms that improve efficiency by minimizing the number of edges that need to be processed and the cost of processing each edge. Experimental results demonstrate that the proposed algorithms achieve orders of magnitude speedup compared to the standard greedy algorithm while greatly expanding the RNN.
30
Sheikholeslami, S. M., M. Esmaeili, and L. Volkmann. "Outer Independent Double Roman Domination Stability in Graphs." Ars Combinatoria 160, no. 1 (2024): 21–29. http://dx.doi.org/10.61091/ars-160-04.
Full textAbstract:
An outer independent double Roman dominating function (OIDRDF) on a graph G is a function f : V ( G ) → { 0 , 1 , 2 , 3 } having the property that (i) if f ( v ) = 0 , then the vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f ( w ) = 3 , and if f ( v ) = 1 , then the vertex v must have at least one neighbor w with f ( w ) ≥ 2 and (ii) the subgraph induced by the vertices assigned 0 under f is edgeless. The weight of an OIDRDF is the sum of its function values over all vertices, and the outer independent double Roman domination number γ o i d R ( G ) is the minimum weight of an OIDRDF on G . The γ o i d R -stability ( γ − o i d R -stability, γ + o i d R -stability) of G , denoted by s t γ o i d R ( G ) ( s t − γ o i d R ( G ) , s t + γ o i d R ( G ) ), is defined as the minimum size of a set of vertices whose removal changes (decreases, increases) the outer independent double Roman domination number. In this paper, we determine the exact values on the γ o i d R -stability of some special classes of graphs, and present some bounds on s t γ o i d R ( G ) . In addition, for a tree T with maximum degree Δ , we show that s t γ o i d R ( T ) = 1 and s t − γ o i d R ( T ) ≤ Δ , and characterize the trees that achieve the upper bound.
31
GUHA, SUMANTA. "PARALLEL COMPUTATION OF INTERNAL AND EXTERNAL FARTHEST NEIGHBORS IN SIMPLE POLYGONS." International Journal of Computational Geometry & Applications 02, no. 02 (1992): 175–90. http://dx.doi.org/10.1142/s0218195992000111.
Full textAbstract:
We present efficient parallel algorithms for two problems in simple polygons: the all-farthest neighbors problem and the external all-farthest neighbors problem. The all-farthest neighbors problem is that of computing, for each vertex p of a simple polygon P, a point ψ(p) in P farthest from p when the distance between p and ψ(p) is measured by the shortest path between them constrained to lie inside P. The external all-farthest neighbors problem is that of computing, for each vertex p of a simple polygon P, a point ϕ(p) on (the boundary of) P farthest from p when the distance between p and ϕ(p) is measured by the shortest path between them constrained to lie outside (the interior of) P. Both our algorithms run in O( log 2 n) time on a CREW PRAM with O(n) processors. Our divide-and-conquer method for the external all-farthest neighbors problem, in fact, leads to a new O(n log n) time serial algorithm that matches the currently best serial algorithm for this problem, but is simpler.
32
Jin, Wei, and Li Tan. "Two-geodesic-transitive graphs which are neighbor cubic or neighbor tetravalent." Filomat 32, no. 7 (2018): 2483–88. http://dx.doi.org/10.2298/fil1807483j.
Full textAbstract:
A vertex triple (u, v, w) with v adjacent to both u and w is called a 2-geodesic if u ? w and u,w are not adjacent. A graph ? is said to be 2-geodesic-transitive if its automorphism group is transitive on both arcs and 2-geodesics. In this paper, a complete classification of 2-geodesic-transitive graphs is given which are neighbor cubic or neighbor tetravalent.
33
Valenzuela-Tripodoro, Juan, Maria Mateos-Camacho, Martin Cera, and Maria Alvarez-Ruiz. "On the Total Version of Triple Roman Domination in Graphs." Mathematics 13, no. 8 (2025): 1277. https://doi.org/10.3390/math13081277.
Full textAbstract:
In this paper, we describe the study of total triple Roman domination. Total triple Roman domination is an assignment of labels from {0,1,2,3,4} to the vertices of a graph such that every vertex is protected by at least three units either on itself or its neighbors while ensuring that none of its neighbors remains unprotected. Formally, a total triple Roman dominating function is a function f:V(G)→{0,1,2,3,4} such that f(N[v])≥|AN(v)|+3, where AN(v) denotes the set of active neighbors of vertex v, i.e., those assigned a positive label. We investigate the algorithmic complexity of the associated decision problem, establish sharp bounds regarding graph structural parameters, and obtain the exact values for several graph families.
34
Paul, Somnath. "Conjugate Laplacian eigenvalues of co-neighbour graphs." Algebra and Discrete Mathematics 33, no. 2 (2022): 108–17. http://dx.doi.org/10.12958/adm1754.
Full textAbstract:
Let G be a simple graph of order n. A vertex subset is called independent if its elements are pairwise non-adjacent. Two vertices in G are co-neighbour vertices if they share the same neighbours. Clearly, if S is a set of pairwise co-neighbour vertices of a graph G, then S is an independent set of G. Let c=a+b√m and c=a−b√m, where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. In [M. Lepovic, On conjugate adjacency matrices of a graph, Discrete Mathematics, 307, 730-738, 2007], the author defined the matrix Ac(G)=[cij]n to be the conjugate adjacency matrix of G, if cij=c for any two adjacent vertices i and j, cij=c for any two nonadjacent vertices i and j,and cij= 0 if i=j. In [S. Paul, Conjugate Laplacian matrices of a graph, Discrete Mathematics, Algorithms and Applications, 10, 1850082, 2018], the author defined the conjugate Laplacian matrix of graphs and described various properties of its eigenvalues and eigenspaces. In this article, we determine certain properties of the conjugate Laplacian eigenvalues and the eigenvectors of a graph with co-neighbour vertices.
35
Wei, Zongtian, Nannan Qi, and Xiaokui Yue. "Vertex-Neighbor-Scattering Number of Bipartite Graphs." International Journal of Foundations of Computer Science 27, no. 04 (2016): 501–9. http://dx.doi.org/10.1142/s012905411650012x.
Full textAbstract:
Let G be a connected graph. A set of vertices [Formula: see text] is called subverted from G if each of the vertices in S and the neighbor of S in G are deleted from G. By G/S we denote the survival subgraph that remains after S is subverted from G. A vertex set S is called a cut-strategy of G if G/S is disconnected, a clique, or ø. The vertex-neighbor-scattering number of G is defined by [Formula: see text], where S is any cut-strategy of G, and ø(G/S) is the number of components of G/S. It is known that this parameter can be used to measure the vulnerability of spy networks and the computing problem of the parameter is NP-complete. In this paper, we discuss the vertex-neighbor-scattering number of bipartite graphs. The NP-completeness of the computing problem of this parameter is proven, and some upper and lower bounds of the parameter are also given.
36
Kandİlcİ, Saadet, Goksen Bacak-Turan, and Refet Polat. "Graph Operations and Neighbor Rupture Degree." Journal of Applied Mathematics 2013 (2013): 1–7. http://dx.doi.org/10.1155/2013/836395.
Full textAbstract:
In a communication network, the vulnerability parameters measure the resistance of the network to disruption of operation after the failure of certain stations or communication links. A vertex subversion strategy of a graph , say , is a set of vertices in whose closed neighborhood is removed from . The survival subgraph is denoted by . The neighbor rupture degree of , , is defined to be , where is any vertex subversion strategy of , is the number of connected components in and is the maximum order of the components of (G. Bacak Turan, 2010). In this paper we give some results for the neighbor rupture degree of the graphs obtained by some graph operations.
37
GU, MEI-MEI, RONG-XIA HAO, and DOND-XUE YANG. "A Short Note on the 1, 2-Good-Neighbor Diagnosability of Balanced Hypercubes." Journal of Interconnection Networks 16, no. 02 (2016): 1650001. http://dx.doi.org/10.1142/s0219265916500018.
Full textAbstract:
Let tc(G) and tg(G) be the conditional diagnosability and g-good-neighbor diagnosability, respectively, of a graph G. The notion of the g-good-neighbor conditional diagnosability is less restrictive as compared with that of the conditional diagnosability in general. Particularly, the conditional faulty set notion requires that, any vertex, faulty or not, have at least one non-faulty neighbor; while the 1-good-neighbor faulty only requires that a non-faulty vertex have at least one non-faulty neighbor. Compared with conditional diagnosability, g-good-neighbor diagnosability is interesting since it characterizes a stronger tolerance capability. In this paper, we investigate the equal relation between t1(BHn) and tc(BHn) for the balanced hypercubes BHn. That is [Formula: see text] for [Formula: see text] under the PMC model and [Formula: see text] for [Formula: see text] under the MM model; Furthermore, the 2-good-neighbor diagnosability t2(BHn) = 4n − 1 for n ≥ 2 under the PMC model and the MM model is obtained.
38
Amjadi, J. "The signed total Roman domatic number of a digraph." Discrete Mathematics, Algorithms and Applications 10, no. 02 (2018): 1850020. http://dx.doi.org/10.1142/s1793830918500209.
Full textAbstract:
Let [Formula: see text] be a finite simple digraph with vertex set [Formula: see text]. A signed total Roman dominating function (STRDF) on a digraph [Formula: see text] is a function [Formula: see text] such that (i) [Formula: see text] for every [Formula: see text], where [Formula: see text] consists of all inner neighbors of [Formula: see text], and (ii) every vertex [Formula: see text] for which [Formula: see text] has an inner neighbor [Formula: see text] for which [Formula: see text]. The weight of an STRDF [Formula: see text] is [Formula: see text]. The signed total Roman domination number [Formula: see text] of [Formula: see text] is the minimum weight of an STRDF on [Formula: see text]. A set [Formula: see text] of distinct STRDFs on [Formula: see text] with the property that [Formula: see text] for each [Formula: see text] is called a signed total Roman dominating family (STRD family) (of functions) on [Formula: see text]. The maximum number of functions in an STRD family on [Formula: see text] is the signed total Roman domatic number of [Formula: see text], denoted by [Formula: see text]. In this paper, we initiate the study of signed total Roman domatic number in digraphs and we present some sharp bounds for [Formula: see text]. In addition, we determine the signed total Roman domatic number of some classes of digraphs.
39
P., Dhanya, and Anil Kumar V. "Equi Neighbor Polynomial of Some Binary Graph Operations." Journal of Combinatorial Mathematics and Combinatorial Computing 119, no. 1 (2024): 35–43. http://dx.doi.org/10.61091/jcmcc119-04.
Full textAbstract:
Let \(G(V,E)\) be a simple graph of order \(n\) with vertex set \(V\) and edge set \(E\). Let \((u, v)\) denote an unordered vertex pair of distinct vertices of \(G\). For a vertex \(u \in G,\) let \(N(u)\) be the set of all vertices of \(G\) which are adjacent to \(u\) in \(G.\) Then for \(0\leq i \leq n-1\), the \(i\)-equi neighbor set of \(G\) is defined as: \(N_{e}(G,i)=\{(u,v):u, v\in V, u\neq v\) and \(|N(u)|=|N(v)|=i\}.\) The equi-neighbor polynomial \(N_{e}[G;x]\) of \(G\) is defined as \(N_{e}[G;x]=\sum_{i=0}^{(n-1)} |N_{e}(G,i)| x^{i}.\) In this paper we discuss the equi-neighbor polynomial of graphs obtained by some binary graph operations.
40
Hamidoune, Y. O., A. Lladó, and S. C. López. "Vertex-transitive graphs that remain connected after failure of a vertex and its neighbors." Journal of Graph Theory 67, no. 2 (2011): 124–38. http://dx.doi.org/10.1002/jgt.20521.
Full text
41
Hayat, Khizar, Muhammad Irfan Ali, Bing-Yuan Cao, and Xiao-Peng Yang. "A New Type-2 Soft Set: Type-2 Soft Graphs and Their Applications." Advances in Fuzzy Systems 2017 (2017): 1–17. http://dx.doi.org/10.1155/2017/6162753.
Full textAbstract:
The correspondence between a vertex and its neighbors has an essential role in the structure of a graph. Type-2 soft sets are also based on the correspondence of primary parameters and underlying parameters. In this study, we present an application of type-2 soft sets in graph theory. We introduce vertex-neighbors based type-2 soft sets overX(set of all vertices of a graph) andE(set of all edges of a graph). Moreover, we introduce some type-2 soft operations in graphs by presenting several examples to demonstrate these new concepts. Finally, we describe an application of type-2 soft graphs in communication networks and present procedure as an algorithm.
42
Goldstone, Richard. "The structure of neighbor disconnected vertex transitive graphs." Discrete Mathematics 202, no. 1-3 (1999): 73–100. http://dx.doi.org/10.1016/s0012-365x(98)00348-3.
Full text
43
Gambrell, Marci J. "Vertex-neighbor-integrity of magnifiers, expanders, and hypercubes." Discrete Mathematics 216, no. 1-3 (2000): 257–66. http://dx.doi.org/10.1016/s0012-365x(99)00352-0.
Full text
44
ATAY ATAKUL, Betül. "Integrity and vertex neighbor integrity of some graphs." Malaya Journal of Matematik 11, no. 03 (2023): 278–85. http://dx.doi.org/10.26637/mjm1103/004.
Full textAbstract:
The integrity $I(G)$ of a noncomplete connected graph $G$ is a measure of network vulnerability and is defined by $I(G)=\min\limits_{S\subset V(G)}\{ |S|+m(G-S)\}$, where $S$ and $m(G-S)$ denote the subset of $V$ and the order of the largest component of $G-S$, respectively. The vertex neigbor integrity denoted as $VNI(G)$ is the concept of the integrity of a connected graph $G$ and is defined by $VNI(G)=\min\limits_{S\subset V(G)}\{|S|+m(G-S)\}$, where $S$ is any vertex subversion strategy of $G$ and $m(G-S)$ is the number of vertices in the largest component of $G-S$. If a network is modelled as a graph, then the integrity number shows not only the difficulty to break down the network but also the damage that has been caused. This article includes several results on the integrity of the $k-ary $ $tree$ $H_{n}^{k}$, the diamond-necklace $N_{k}$, the diamond-chain $L_{k}$ and the thorn graph of the cycle graph and the vertex neighbor integrity of the $H_{n}^{2}$, $H_{n}^{3}$.
45
Tian, Shuang Liang, and Qian Wang. "Adjacent Vertex Distinguishing Distance Coloring of Grids." Applied Mechanics and Materials 644-650 (September 2014): 2416–18. http://dx.doi.org/10.4028/www.scientific.net/amm.644-650.2416.
Full textAbstract:
A-distance coloringof is said to be adjacent vertex distinguishing if this coloring satisfy for any pair of adjacent vertices and in, wheredenotes the set of colors that are received by the vertex and all neighbors of with respect to. The minimum number of colors necessary to adjacent vertex distinguishing-distance color, is denoted by. In this paper, we give the exact values of forand, where denotes the-dimensional grid.
46
Nash, Alex, Sven Koenig, and Craig Tovey. "Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D." Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (2010): 147–54. http://dx.doi.org/10.1609/aaai.v24i1.7566.
Full textAbstract:
Grids with blocked and unblocked cells are often used to represent continuous 2D and 3D environments in robotics and video games. The shortest paths formed by the edges of 8-neighbor 2D grids can be up to 8% longer than the shortest paths in the continuous environment. Theta* typically finds much shorter paths than that by propagating information along graph edges (to achieve short runtimes) without constraining paths to be formed by graph edges (to find short "any-angle" paths). We show in this paper that the shortest paths formed by the edges of 26-neighbor 3D grids can be 13% longer than the shortest paths in the continuous environment, which highlights the need for smart path planning algorithms in 3D. Theta* can be applied to 3D grids in a straight-forward manner, but it performs a line-of-sight check for each unexpanded visible neighbor of each expanded vertex and thus it performs many more line-of-sight checks per expanded vertex on a 26-neighbor 3D grid than on an 8-neighbor 2D grid. We therefore introduce Lazy Theta*, a variant of Theta* which uses lazy evaluation to perform only one line-of-sight check per expanded vertex (but with slightly more expanded vertices). We show experimentally that Lazy Theta* finds paths faster than Theta* on 26-neighbor 3D grids, with one order of magnitude fewer line-of-sight checks and without an increase in path length.
47
Nash, Alex, Sven Koenig, and Craig Tovey. "Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D." Proceedings of the International Symposium on Combinatorial Search 1, no. 1 (2010): 153–54. http://dx.doi.org/10.1609/socs.v1i1.18152.
Full textAbstract:
Grids with blocked and unblocked cells are often used to represent continuous 2D and 3D environments in robotics and video games. The shortest paths formed by the edges of 8-neighbor 2D grids can be up to ≈ 8% longer than the shortest paths in the continuous environment. Theta* typically finds much shorter paths than that by propagating information along graph edges (to achieve short runtimes) without constraining paths to be formed by graph edges (to find short “any-angle” paths). We show in this paper that the shortest paths formed by the edges of 26-neighbor 3D grids can be ≈ 13% longer than the shortest paths in the continuous environment, which highlights the need for smart path planning algorithms in 3D. Theta* can be applied to 3D grids in a straight-forward manner, but it performs a line-of-sight check for each unexpanded visible neighbor of each expanded vertex and thus it performs many more line-of-sight checks per expanded vertex on a 26-neighbor 3D grid than on an 8-neighbor 2D grid. We therefore introduce Lazy Theta*, a variant of Theta* which uses lazy evaluation to perform only one line-of-sight check per expanded vertex (but with slightly more expanded vertices). We show experimentally that Lazy Theta* finds paths faster than Theta* on 26-neighbor 3D grids, with one order of magnitude fewer line-of-sight checks and without an increase in path length.
48
Lanchier, N., and S. Reed. "The role of cooperation in spatially explicit economical systems." Advances in Applied Probability 50, no. 3 (2018): 743–58. http://dx.doi.org/10.1017/apr.2018.34.
Full textAbstract:
Abstract In this paper we are concerned with a model in econophysics, the subfield of statistical physics that applies concepts from traditional physics to economics. Our model is an example of an interacting particle system with disorder, meaning that some of the transition rates are not identical but rather drawn from a fixed distribution. Economical agents are represented by the vertices of a connected graph and are characterized by the number of coins they possess. Agents independently spend one coin at rate one for their basic need, earn one coin at a rate chosen independently from a distribution ϕ, and exchange money at rate µ with one of their nearest neighbors, with the richest neighbor giving one coin to the other neighbor. If an agent needs to spend one coin when his/her fortune is at 0, he/she dies, i.e. the corresponding vertex is removed from the graph. Our first results focus on the two extreme cases of lack of cooperation µ=0 and perfect cooperation µ = ∞ for finite connected graphs. These results suggest that, when overall the agents earn more than they spend, cooperation is beneficial for the survival of the population, whereas when overall the agents earn less than they spend, cooperation becomes detrimental. We also study the infinite one-dimensional system. In this case, when the agents earn less than they spend on average, the density of agents that die eventually is bounded from below by a positive constant that does not depend on the initial number of coins per agent or the level of cooperation.
49
Adegbindin, Mourchid, Alain Hertz, and Martine Bellaïche. "A new efficient RLF-like algorithm for the vertex coloring problem." Yugoslav Journal of Operations Research 26, no. 4 (2016): 441–56. http://dx.doi.org/10.2298/yjor151102003a.
Full textAbstract:
The Recursive Largest First (RLF) algorithm is one of the most popular greedy heuristics for the vertex coloring problem. It sequentially builds color classes on the basis of greedy choices. In particular, the first vertex placed in a color class C is one with a maximum number of uncolored neighbors, and the next vertices placed in C are chosen so that they have as many uncolored neighbors which cannot be placed in C. These greedy choices can have a significant impact on the performance of the algorithm, which explains why we propose alternative selection rules. Computational experiments on 63 difficult DIMACS instances show that the resulting new RLF-like algorithm, when compared with the standard RLF, allows to obtain a reduction of more than 50% of the gap between the number of colors used and the best known upper bound on the chromatic number. The new greedy algorithm even competes with basic metaheuristics for the vertex coloring problem.
50
Bailey, James, Craig Tovey, Tansel Uras, Sven Koenig, and Alex Nash. "Path Planning on Grids: The Effect of Vertex Placement on Path Length." Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 11, no. 1 (2021): 108–14. http://dx.doi.org/10.1609/aiide.v11i1.12808.
Full textAbstract:
Video-game designers often tessellate continuous 2-dimensional terrain into a grid of blocked and unblocked square cells. The three main ways to calculate short paths on such a grid are to determine truly shortest paths, shortest vertex paths and shortest grid paths, listed here in decreasing order of computation time and increasing order of resulting path length. We show that, for both vertex and grid paths on both 4-neighbor and 8-neighbor grids, placing vertices at cell corners rather than at cell centers tends to result in shorter paths. We quantify the advantage of cell corners over cell centers theoretically with tight worst-case bounds on the ratios of path lengths, and empirically on a large set of benchmark test cases. We also quantify the advantage of 8-neighbor grids over 4-neighbor grids.