On L(2,1)-labellings of distance graphs

The L(2,1)-labelling number of distance graphs G(D), denoted by λ(D), isstudied. It is shown that distance graphs satisfy λ(G) ≤Δ~2. Moreover, we prove λ({1,2, ..., k})=2k +2 and λ({1,3,..., 2k -1}) =2k + 2 for any fixed positive integer k. Suppose k, a ∈ N and k,a≥2. If k≥a, then λ({a, a + 1,..., a + k - 1}) = 2(a + k-1). Otherwise, λ({a, a + 1, ..., a + k- 1}) ≤min{2(a + k-1), 6k -2}. When D consists of two positive integers,6≤λ(D)≤8. For thespecial distance sets D = {k, k + 1}(any k ∈N), the upper bound of λ(D) is improved to 7.

Coloring of some integer distance graphs

An integer distance graph is a graph G(Z, D) with the integer set Z as vertexset, in which an edge joining two vertices u and v if and only if | u - v | ∈ D, where D is a setof natural numbers. Using a related theorem in combinatorics and some conclusions known to us in thecoloring of the distance graph, the chromatic number _X(G) is determined in this paper that is ofthe distance graph G(Z, D) for some finite distance sets D containing {2, 3} with D = 4 andcontaining {2, 3, 5} with | D | = 5 by the method in which the combination of a few periodiccolorings.

L(2,1)-labeling problem on distance graphs

L (2, 1)-labeling number, λ(G( Z , D)) , of distance graph G( Z , D) is studied. For general finite distance set D , it is shown that 2D+2≤λ(G( Z , D))≤D 2+3D. Furthermore, λ(G( Z , D)) ≤8 when D consists of two prime positive odd integers is proved. Finally, a new concept to study the upper bounds of λ(G) for some special D is introduced. For these sets, the upper bound is improved to 7.

Circular Chromatic Numbers of Some Distance Graphs

The circular chromatic number of a graph is an important parameter of a graph. The distance graph G(Z,D) , with a distance set D , is the infinite graph with vertex set Z={0,±1,±2,...} in which two vertices x and y are adjacent iff y-x∈D . This paper determines the circular chromatic numbers of two classes of distance graphs G(Z,D m,k,k+1 ) and G(Z,D m,k,k+1,k+2 ).

A Note on <i>n</i>-Set Distance-Labelings of Graphs

This note is considered as a sequel of Yeh [1]. Here, we present a generalized (vertex) distance labeling (labeling vertices under constraints depending the on distance between vertices) of a graph. Instead of assigning a number (label) to each vertex, we assign a set of numbers to each vertex under given conditions. Some basic results are given in the first part of the note. Then we study a particular class of this type of labelings on several classes of graphs.

Federated Graph Learning Based on Graph Distance Computing

Federated learning is a classic of privacy-preserving learning, which enables collaborative learning without sharing data. Structured data has become the mainstream of current applications, where there is a correlation between samples in the same dataset, which can be represented by a graph. Federated graph learning (FGL) is the integration of structured data into federated learning, assuming that each user has structured graph representation data and uses graph learning models for training. This article proposes an FGL algorithm based on graph distance calculation, which determines the similarity of users in terms of graph distance, then clusters users, and aggregates local models of users in the same cluster. This algorithm can adjust the number of clusters by changing the threshold (the larger the threshold, the fewer clusters and the more users in each cluster, and vice versa), thereby controlling the scope of user collaboration.

An Intelligent Graph Edit Distance-Based Approach for Finding Business Process Similarities

There are numerous application areas of computing similarity between process models.It includes finding similar models from a repository,controlling redundancy of process models,and finding corresponding activities between a pair of process models.The similarity between two process models is computed based on their similarity between labels,structures,and execution behaviors.Several attempts have been made to develop similarity techniques between activity labels,as well as their execution behavior.However,a notable problem with the process model similarity is that two process models can also be similar if there is a structural variation between them.However,neither a benchmark dataset exists for the structural similarity between process models nor there exist an effective technique to compute structural similarity.To that end,we have developed a large collection of process models in which structural changes are handcrafted while preserving the semantics of the models.Furthermore,we have used a machine learning-based approach to compute the similarity between a pair of process models having structural and label differences.Finally,we have evaluated the proposed approach using our generated collection of process models.

Solid model edit distance: a multi-application and multi-level schema for CAD model retrieval

We present the solid model edit distance(SMED),a powerful and flexible paradigm for exploiting shape similarities amongst CAD models.It is designed to measure the magnitude of distortions between two CAD models in boundary representation(B-rep).We give the formal definition by analogy with graph edit distance,one of the most popular graph matching methods.To avoid the expensive computational cost potentially caused by exact computation,an approximate procedure based on the alignment of local structure sets is provided in addition.In order to verify the flexibility,we make intensive investigations on three typical applications in manufacturing industry,and describe how our method can be adapted to meet the various requirements.Furthermore,a multilevel method is proposed to make further improvements of the presented algorithm on both effectiveness and efficiency,in which the models are hierarchically segmented into the configurations of features.Experiment results show that SMED serves as a reasonable measurement of shape similarity for CAD models,and the proposed approach provides remarkable performance on a real-world CAD model database.

On Connected Graphs with Distance Eigenvalue-1 of Multiplicity at Least n-4

Let G_(n)([-1]^(i))denote the set of all connected graphs on n vertices having distance eigenvalue-1 of multiplicity i.By using the distribution of the third largest distance eigenvalue and the second least distance eigenvalue of a connected graph,in this paper we completely characterize the graphs in G_(n)([-1]^(i)),where i=n-1,n-2,n-3 or n-4.

An Optimized Approach to Vehicle-Type Classification Using a Convolutional Neural Network

There are numerous application areas of computing similarity between process models.It includes finding similar models from a repository,controlling redundancy of process models,and finding corresponding activities between a pair of process models.The similarity between two process models is computed based on their similarity between labels,structures,and execution behaviors.Several attempts have been made to develop similarity techniques between activity labels,as well as their execution behavior.However,a notable problem with the process model similarity is that two process models can also be similar if there is a structural variation between them.However,neither a benchmark dataset exists for the structural similarity between process models nor there exist an effective technique to compute structural similarity.To that end,we have developed a large collection of process models in which structural changes are handcrafted while preserving the semantics of the models.Furthermore,we have used a machine learning-based approach to compute the similarity between a pair of process models having structural and label differences.Finally,we have evaluated the proposed approach using our generated collection of process models.

Learning from the crowd:Road infrastructure monitoring system

The condition of the road infrastructure has severe impacts on the road safety, driving comfort, and on the rolling resistance. Therefore, the road infrastructure must be moni- tored comprehensively and in regular intervals to identify damaged road segments and road hazards. Methods have been developed to comprehensively and automatically digitize the road infrastructure and estimate the road quality, which are based on vehicle sensors and a supervised machine learning classification. Since different types of vehicles have various suspension systems with different response functions, one classifier cannot be taken over to other vehicles. Usually, a high amount of time is needed to acquire training data for each individual vehicle and classifier. To address this problem, the methods to collect training data automatically for new vehicles based on the comparison of trajectories of untrained and trained vehicles have been developed. The results show that the method based on a k-dimensional tree and Euclidean distance performs best and is robust in transferring the information of the road surface from one vehicle to another. Furthermore, this method offers the possibility to merge the output and road infrastructure information from multiple vehicles to enable a more robust and precise prediction of the ground truth.

Scale-Free Percolation in Continuum Space

The study of real-life network modeling has become very popular in recent years.An attractive model is the scale-free percolation model on the lattice Zd,d≥1,because it fulfills several stylized facts observed in large real-life networks.We adopt this model to continuum space which leads to a heterogeneous random-connection model on Rd:Particles are generated by a homogeneous marked Poisson point process on Rd,and the probability of an edge between two particles is determined by their marks and their distance.In this model we study several properties such as the degree distributions,percolation properties and graph distances.

Inexact graph matching using a hierarchy of matching processes

Inexact graph matching algorithms have proved to be useful in many applications,such as character recognition,shape analysis,and image analysis. Inexact graph matching is,however,inherently an NP-hard problem with exponential computational complexity. Much of the previous research has focused on solving this problem using heuristics or estimations. Unfortunately,many of these techniques do not guarantee that an optimal solution will be found. It is the aim of the proposed algorithm to reduce the complexity of the inexact graph matching process,while still producing an optimal solution for a known application. This is achieved by greatly simplifying each individual matching process,and compensating for lost robustness by producing a hierarchy of matching processes. The creation of each matching process in the hierarchy is driven by an application-specific criterion that operates at the subgraph scale. To our knowledge,this problem has never before been approached in this manner. Results show that the proposed algorithm is faster than two existing methods based on graph edit operations.The proposed algorithm produces accurate results in terms of matching graphs,and shows promise for the application of shape matching. The proposed algorithm can easily be extended to produce a sub-optimal solution if required.