Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 1051

Search results for: Distance in graphs

1051 Terminal Wiener Index for Graph Structures

Authors: J. Baskar Babujee, J. Senbagamalar,

Abstract:

The topological distance between a pair of vertices i and j, which is denoted by d(vi, vj), is the number of edges of the shortest path joining i and j. The Wiener index W(G) is the sum of distances between all pairs of vertices of a graph G. W(G) = i

Keywords: Graph, Degree, Distance, Pendent vertex, Wiener index, Tree.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1917
1050 A Study about the Distribution of the Spanning Ratios of Yao Graphs

Authors: Maryam Hsaini, Mostafa Nouri-Baygi

Abstract:

A critical problem in wireless sensor networks is limited battery and memory of nodes. Therefore, each node in the network could maintain only a subset of its neighbors to communicate with. This will increase the battery usage in the network because each packet should take more hops to reach its destination. In order to tackle these problems, spanner graphs are defined. Since each node has a small degree in a spanner graph and the distance in the graph is not much greater than its actual geographical distance, spanner graphs are suitable candidates to be used for the topology of a wireless sensor network. In this paper, we study Yao graphs and their behavior for a randomly selected set of points. We generate several random point sets and compare the properties of their Yao graphs with the complete graph. Based on our data sets, we obtain several charts demonstrating how Yao graphs behave for a set of randomly chosen point set. As the results show, the stretch factor of a Yao graph follows a normal distribution. Furthermore, the stretch factor is in average far less than the worst case stretch factor proved for Yao graphs in previous results. Furthermore, we use Yao graph for a realistic point set and study its stretch factor in real world.

Keywords: Wireless sensor network, spanner graph, Yao Graph.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 425
1049 Using Spectral Vectors and M-Tree for Graph Clustering and Searching in Graph Databases of Protein Structures

Authors: Do Phuc, Nguyen Thi Kim Phung

Abstract:

In this paper, we represent protein structure by using graph. A protein structure database will become a graph database. Each graph is represented by a spectral vector. We use Jacobi rotation algorithm to calculate the eigenvalues of the normalized Laplacian representation of adjacency matrix of graph. To measure the similarity between two graphs, we calculate the Euclidean distance between two graph spectral vectors. To cluster the graphs, we use M-tree with the Euclidean distance to cluster spectral vectors. Besides, M-tree can be used for graph searching in graph database. Our proposal method was tested with graph database of 100 graphs representing 100 protein structures downloaded from Protein Data Bank (PDB) and we compare the result with the SCOP hierarchical structure.

Keywords: Eigenvalues, m-tree, graph database, protein structure, spectra graph theory.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1387
1048 On Suborbital Graphs of the Congruence Subgroup r 0(N)

Authors: Bahadir O. Guler, Serkan Kader, Murat Besenk

Abstract:

In this paper we examine some properties of suborbital graphs for the congruence subgroup r 0 (N) . Then we give necessary and sufficient conditions for graphs to have triangels.

Keywords: Congruence subgroup, Imprimitive action, Modulargroup, Suborbital graphs.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1239
1047 All-Pairs Shortest-Paths Problem for Unweighted Graphs in O(n2 log n) Time

Authors: Udaya Kumar Reddy K. R, K. Viswanathan Iyer

Abstract:

Given a simple connected unweighted undirected graph G = (V (G), E(G)) with |V (G)| = n and |E(G)| = m, we present a new algorithm for the all-pairs shortest-path (APSP) problem. The running time of our algorithm is in O(n2 log n). This bound is an improvement over previous best known O(n2.376) time bound of Raimund Seidel (1995) for general graphs. The algorithm presented does not rely on fast matrix multiplication. Our algorithm with slight modifications, enables us to compute the APSP problem for unweighted directed graph in time O(n2 log n), improving a previous best known O(n2.575) time bound of Uri Zwick (2002).

Keywords: Distance in graphs, Dynamic programming, Graphalgorithms, Shortest paths.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3385
1046 Lower Bounds of Some Small Ramsey Numbers

Authors: Decha Samana, Vites Longani

Abstract:

For positive integer s and t, the Ramsey number R(s, t) is the least positive integer n such that for every graph G of order n, either G contains Ks as a subgraph or G contains Kt as a subgraph. We construct the circulant graphs and use them to obtain lower bounds of some small Ramsey numbers.

Keywords: Lower bound, Ramsey numbers, Graphs, Distance line.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1212
1045 Graphs with Metric Dimension Two-A Characterization

Authors: Sudhakara G, Hemanth Kumar A.R

Abstract:

In this paper, we define distance partition of vertex set of a graph G with reference to a vertex in it and with the help of the same, a graph with metric dimension two (i.e. β (G) = 2 ) is characterized. In the process, we develop a polynomial time algorithm that verifies if the metric dimension of a given graph G is two. The same algorithm explores all metric bases of graph G whenever β (G) = 2 . We also find a bound for cardinality of any distance partite set with reference to a given vertex, when ever β (G) = 2 . Also, in a graph G with β (G) = 2 , a bound for cardinality of any distance partite set as well as a bound for number of vertices in any sub graph H of G is obtained in terms of diam H .

Keywords: Metric basis, Distance partition, Metric dimension.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1609
1044 Isomorphism on Fuzzy Graphs

Authors: A.Nagoor Gani, J.Malarvizhi

Abstract:

In this paper, the order, size and degree of the nodes of the isomorphic fuzzy graphs are discussed. Isomorphism between fuzzy graphs is proved to be an equivalence relation. Some properties of self complementary and self weak complementary fuzzy graphs are discussed.

Keywords: complementary fuzzy graphs, co-weak isomorphism, equivalence relation, fuzzy relation, weak isomorphism.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3890
1043 An Improved Method to Compute Sparse Graphs for Traveling Salesman Problem

Authors: Y. Wang

Abstract:

The Traveling salesman problem (TSP) is NP-hard in combinatorial optimization. The research shows the algorithms for TSP on the sparse graphs have the shorter computation time than those for TSP according to the complete graphs. We present an improved iterative algorithm to compute the sparse graphs for TSP by frequency graphs computed with frequency quadrilaterals. The iterative algorithm is enhanced by adjusting two parameters of the algorithm. The computation time of the algorithm is O(CNmaxn2) where C is the iterations, Nmax is the maximum number of frequency quadrilaterals containing each edge and n is the scale of TSP. The experimental results showed the computed sparse graphs generally have less than 5n edges for most of these Euclidean instances. Moreover, the maximum degree and minimum degree of the vertices in the sparse graphs do not have much difference. Thus, the computation time of the methods to resolve the TSP on these sparse graphs will be greatly reduced.

Keywords: Frequency quadrilateral, iterative algorithm, sparse graph, traveling salesman problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 640
1042 Reductions of Control Flow Graphs

Authors: Robert Gold

Abstract:

Control flow graphs are a well-known representation of the sequential control flow structure of programs with a multitude of applications. Not only single functions but also sets of functions or complete programs can be modeled by control flow graphs. In this case the size of the graphs can grow considerably and thus makes it difficult for software engineers to analyze the control flow. Graph reductions are helpful in this situation. In this paper we define reductions to subsets of nodes. Since executions of programs are represented by paths through the control flow graphs, paths should be preserved. Furthermore, the composition of reductions makes a stepwise analysis approach possible.

Keywords: Control flow graph, graph reduction.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3333
1041 2D Structured Non-Cyclic Fuzzy Graphs

Authors: T. Pathinathan, M. Peter

Abstract:

Fuzzy graphs incorporate concepts from graph theory with fuzzy principles. In this paper, we make a study on the properties of fuzzy graphs which are non-cyclic and are of two-dimensional in structure. In particular, this paper presents 2D structure or the structure of double layer for a non-cyclic fuzzy graph whose underlying crisp graph is non-cyclic. In any graph structure, introducing 2D structure may lead to an inherent cycle. We propose relevant conditions for 2D structured non-cyclic fuzzy graphs. These conditions are extended even to fuzzy graphs of the 3D structure. General theoretical properties that are studied for any fuzzy graph are verified to 2D structured or double layered fuzzy graphs. Concepts like Order, Degree, Strong and Size for a fuzzy graph are studied for 2D structured or double layered non-cyclic fuzzy graphs. Using different types of fuzzy graphs, the proposed concepts relating to 2D structured fuzzy graphs are verified.

Keywords: Double layered fuzzy graph, double layered non-cyclic fuzzy graph, strong, order, degree and size.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 521
1040 Computing Maximum Uniquely Restricted Matchings in Restricted Interval Graphs

Authors: Swapnil Gupta, C. Pandu Rangan

Abstract:

A uniquely restricted matching is defined to be a matching M whose matched vertices induces a sub-graph which has only one perfect matching. In this paper, we make progress on the open question of the status of this problem on interval graphs (graphs obtained as the intersection graph of intervals on a line). We give an algorithm to compute maximum cardinality uniquely restricted matchings on certain sub-classes of interval graphs. We consider two sub-classes of interval graphs, the former contained in the latter, and give O(|E|^2) time algorithms for both of them. It is to be noted that both sub-classes are incomparable to proper interval graphs (graphs obtained as the intersection graph of intervals in which no interval completely contains another interval), on which the problem can be solved in polynomial time.

Keywords: Uniquely restricted matching, interval graph, design and analysis of algorithms, matching, induced matching, witness counting.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1238
1039 Low Complexity Regular LDPC codes for Magnetic Storage Devices

Authors: Gabofetswe Malema, Michael Liebelt

Abstract:

LDPC codes could be used in magnetic storage devices because of their better decoding performance compared to other error correction codes. However, their hardware implementation results in large and complex decoders. This one of the main obstacles the decoders to be incorporated in magnetic storage devices. We construct small high girth and rate 2 columnweight codes from cage graphs. Though these codes have low performance compared to higher column weight codes, they are easier to implement. The ease of implementation makes them more suitable for applications such as magnetic recording. Cages are the smallest known regular distance graphs, which give us the smallest known column-weight 2 codes given the size, girth and rate of the code.

Keywords: Structured LDPC codes, cage graphs.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1941
1038 Low Complexity, High Performance LDPC Codes Based on Defected Fullerene Graphs

Authors: Ashish Goswami, Rakesh Sharma

Abstract:

In this paper, LDPC Codes based on defected fullerene graphs have been generated. And it is found that the codes generated are fast in encoding and better in terms of error performance on AWGN Channel.

Keywords: LDPC Codes, Fullerene Graphs, Defected Fullerene Graphs.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1604
1037 Nullity of t-Tupple Graphs

Authors: Khidir R. Sharaf, Didar A. Ali

Abstract:

The nullity η(G) of a graph is the occurrence of zero as an eigenvalue in its spectra. A zero-sum weighting of a graph G is real valued function, say f from vertices of G to the set of real numbers, provided that for each vertex of G the summation of the weights f(w) over all neighborhood w of v is zero for each v in G.A high zero-sum weighting of G is one that uses maximum number of non-zero independent variables. If G is graph with an end vertex, and if H is an induced subgraph of G obtained by deleting this vertex together with the vertex adjacent to it, then, η(G)= η(H). In this paper, a high zero-sum weighting technique and the endvertex procedure are applied to evaluate the nullity of t-tupple and generalized t-tupple graphs are derived  and determined for some special types of graphs,

 Also, we introduce and prove some important results about the t-tupple coalescence, Cartesian and Kronecker products of nut graphs.

Keywords: Graph theory, Graph spectra, Nullity of graphs.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1722
1036 On Detour Spectra of Some Graphs

Authors: S.K.Ayyaswamy, S.Balachandran

Abstract:

The Detour matrix (DD) of a graph has for its ( i , j) entry the length of the longest path between vertices i and j. The DD-eigenvalues of a connected graph G are the eigenvalues for its detour matrix, and they form the DD-spectrum of G. The DD-energy EDD of the graph G is the sum of the absolute values of its DDeigenvalues. Two connected graphs are said to be DD- equienergetic if they have equal DD-energies. In this paper, the DD- spectra of a variety of graphs and their DD-energies are calculated.

Keywords: Detour eigenvalue (of a graph), detour spectrum(of a graph), detour energy(of a graph), detour - equienergetic graphs.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1344
1035 On Speeding Up Support Vector Machines: Proximity Graphs Versus Random Sampling for Pre-Selection Condensation

Authors: Xiaohua Liu, Juan F. Beltran, Nishant Mohanchandra, Godfried T. Toussaint

Abstract:

Support vector machines (SVMs) are considered to be the best machine learning algorithms for minimizing the predictive probability of misclassification. However, their drawback is that for large data sets the computation of the optimal decision boundary is a time consuming function of the size of the training set. Hence several methods have been proposed to speed up the SVM algorithm. Here three methods used to speed up the computation of the SVM classifiers are compared experimentally using a musical genre classification problem. The simplest method pre-selects a random sample of the data before the application of the SVM algorithm. Two additional methods use proximity graphs to pre-select data that are near the decision boundary. One uses k-Nearest Neighbor graphs and the other Relative Neighborhood Graphs to accomplish the task.

Keywords: Machine learning, data mining, support vector machines, proximity graphs, relative-neighborhood graphs, k-nearestneighbor graphs, random sampling, training data condensation.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1720
1034 On Strong(Weak) Domination in Fuzzy Graphs

Authors: C.Natarajan, S.K.Ayyaswamy

Abstract:

Let G be a fuzzy graph. Then D Ôèå V is said to be a strong (weak) fuzzy dominating set of G if every vertex v ∈ V -D is strongly (weakly) dominated by some vertex u in D. We denote a strong (weak) fuzzy dominating set by sfd-set (wfd-set). The minimum scalar cardinality of a sfd-set (wfd-set) is called the strong (weak) fuzzy domination number of G and it is denoted by γsf (G)γwf (G). In this paper we introduce the concept of strong (weak) domination in fuzzy graphs and obtain some interesting results for this new parameter in fuzzy graphs.

Keywords: Fuzzy graphs, fuzzy domination, strong (weak) fuzzy domination number.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3673
1033 On Chvátal’s Conjecture for the Hamiltonicity of 1-Tough Graphs and Their Complements

Authors: Shin-Shin Kao, Yuan-Kang Shih, Hsun Su

Abstract:

In this paper, we show that the conjecture of Chv tal, which states that any 1-tough graph is either a Hamiltonian graph or its complement contains a specific graph denoted by F, does not hold in general. More precisely, it is true only for graphs with six or seven vertices, and is false for graphs with eight or more vertices. A theorem is derived as a correction for the conjecture.

Keywords: Complement, degree sum, Hamiltonian, tough.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 476
1032 Diameter of Zero Divisor Graphs of Finite Direct Product of Lattices
1031 A Distance Function for Data with Missing Values and Its Application

Authors: Loai AbdAllah, Ilan Shimshoni

Abstract:

Missing values in data are common in real world applications. Since the performance of many data mining algorithms depend critically on it being given a good metric over the input space, we decided in this paper to define a distance function for unlabeled datasets with missing values. We use the Bhattacharyya distance, which measures the similarity of two probability distributions, to define our new distance function. According to this distance, the distance between two points without missing attributes values is simply the Mahalanobis distance. When on the other hand there is a missing value of one of the coordinates, the distance is computed according to the distribution of the missing coordinate. Our distance is general and can be used as part of any algorithm that computes the distance between data points. Because its performance depends strongly on the chosen distance measure, we opted for the k nearest neighbor classifier to evaluate its ability to accurately reflect object similarity. We experimented on standard numerical datasets from the UCI repository from different fields. On these datasets we simulated missing values and compared the performance of the kNN classifier using our distance to other three basic methods. Our  experiments show that kNN using our distance function outperforms the kNN using other methods. Moreover, the runtime performance of our method is only slightly higher than the other methods.

Keywords: Missing values, Distance metric, Bhattacharyya distance.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2510
1030 Problem Solving in Chilean Higher Education: Figurations Prior in Interpretations of Cartesian Graphs

Authors: Verónica Díaz

Abstract:

A Cartesian graph, as a mathematical object, becomes a tool for configuration of change. Its best comprehension is done through everyday life problem-solving associated with its representation. Despite this, the current educational framework favors general graphs, without consideration of their argumentation. Students are required to find the mathematical function without associating it to the development of graphical language. This research describes the use made by students of configurations made prior to Cartesian graphs with regards to an everyday life problem related to a time and distance variation phenomenon. The theoretical framework describes the function conditions of study and their modeling. This is a qualitative, descriptive study involving six undergraduate case studies that were carried out during the first term in 2016 at University of Los Lagos. The research problem concerned the graphic modeling of a real person’s movement phenomenon, and two levels of analysis were identified. The first level aims to identify local and global graph interpretations; a second level describes the iconicity and referentiality degree of an image. According to the results, students were able to draw no figures before the Cartesian graph, highlighting the need for students to represent the context and the movement of which causes the phenomenon change. From this, they managed Cartesian graphs representing changes in position, therefore, achieved an overall view of the graph. However, the local view only indicates specific events in the problem situation, using graphic and verbal expressions to represent movement. This view does not enable us to identify what happens on the graph when the movement characteristics change based on possible paths in the person’s walking speed.

Keywords: Cartesian graphs, higher education, movement modeling, problem solving.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 875
1029 Skolem Sequences and Erdosian Labellings of m Paths with 2 and 3 Vertices

Authors: H. V. Chen

Abstract:

Assume that we have m identical graphs where the graphs consists of paths with k vertices where k is a positive integer. In this paper, we discuss certain labelling of the m graphs called c-Erdösian for some positive integers c. We regard labellings of the vertices of the graphs by positive integers, which induce the edge labels for the paths as the sum of the two incident vertex labels. They have the property that each vertex label and edge label appears only once in the set of positive integers {c, . . . , c+6m- 1}. Here, we show how to construct certain c-Erdösian of m paths with 2 and 3 vertices by using Skolem sequences.

Keywords: c-Erdösian, Skolem sequences, magic labelling

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 982
1028 N-Sun Decomposition of Complete Graphs and Complete Bipartite Graphs

Authors: R. Anitha, R. S. Lekshmi

Abstract:

Graph decompositions are vital in the study of combinatorial design theory. Given two graphs G and H, an H-decomposition of G is a partition of the edge set of G into disjoint isomorphic copies of H. An n-sun is a cycle Cn with an edge terminating in a vertex of degree one attached to each vertex. In this paper we have proved that the complete graph of order 2n, K2n can be decomposed into n-2 n-suns, a Hamilton cycle and a perfect matching, when n is even and for odd case, the decomposition is n-1 n-suns and a perfect matching. For an odd order complete graph K2n+1, delete the star subgraph K1, 2n and the resultant graph K2n is decomposed as in the case of even order. The method of building n-suns uses Walecki's construction for the Hamilton decomposition of complete graphs. A spanning tree decomposition of even order complete graphs is also discussed using the labeling scheme of n-sun decomposition. A complete bipartite graph Kn, n can be decomposed into n/2 n-suns when n/2 is even. When n/2 is odd, Kn, n can be decomposed into (n-2)/2 n-suns and a Hamilton cycle.

Keywords: Hamilton cycle, n-sun decomposition, perfectmatching, spanning tree.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2058
1027 Differences in Students` Satisfaction with Distance Learning Studies

Authors: Ana Horvat, Maja Krsmanovic, Mladen Djuric

Abstract:

Rapid growth of distance learning resulted in importance to conduct research on students- satisfaction with distance learning because differences in students- satisfaction might influence educational opportunities for learning in a relevant Web-based environment. In line with this, this paper deals with satisfaction of students with distance module at Faculty of organizational sciences (FOS) in Serbia as well as some factors affecting differences in their satisfaction . We have conducted a research on a population of 68 first-year students of distance learning studies at FOS. Using statistical techniques, we have found out that there is no significant difference in students- satisfaction with distance learning module between men and women. In the same way, we also concluded that there is a difference in satisfaction with distance learning module regarding to student-s perception of opportunity to gain knowledge as the classic students.

Keywords: distance learning, students' satisfaction

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2170
1026 OWA Operators in Generalized Distances

Authors: José M. Merigó, Anna M. Gil-Lafuente

Abstract:

Different types of aggregation operators such as the ordered weighted quasi-arithmetic mean (Quasi-OWA) operator and the normalized Hamming distance are studied. We introduce the use of the OWA operator in generalized distances such as the quasiarithmetic distance. We will call these new distance aggregation the ordered weighted quasi-arithmetic distance (Quasi-OWAD) operator. We develop a general overview of this type of generalization and study some of their main properties such as the distinction between descending and ascending orders. We also consider different families of Quasi-OWAD operators such as the Minkowski ordered weighted averaging distance (MOWAD) operator, the ordered weighted averaging distance (OWAD) operator, the Euclidean ordered weighted averaging distance (EOWAD) operator, the normalized quasi-arithmetic distance, etc.

Keywords: Aggregation operators, Distance measures, Quasi- OWA operator.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1471
1025 Analyzing Methods of the Relation between Concepts based on a Concept Hierarchy

Authors: Ke Lu, Tetsuya Furukawa

Abstract:

Data objects are usually organized hierarchically, and the relations between them are analyzed based on a corresponding concept hierarchy. The relation between data objects, for example how similar they are, are usually analyzed based on the conceptual distance in the hierarchy. If a node is an ancestor of another node, it is enough to analyze how close they are by calculating the distance vertically. However, if there is not such relation between two nodes, the vertical distance cannot express their relation explicitly. This paper tries to fill this gap by improving the analysis method for data objects based on hierarchy. The contributions of this paper include: (1) proposing an improved method to evaluate the vertical distance between concepts; (2) defining the concept horizontal distance and a method to calculate the horizontal distance; and (3) discussing the methods to confine a range by the horizontal distance and the vertical distance, and evaluating the relation between concepts.

Keywords: Concept Hierarchy, Horizontal Distance, Relation Analysis, Vertical Distance

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1027
1024 A Hamiltonian Decomposition of 5-star

Authors: Walter Hussak, Heiko Schröder

Abstract:

Star graphs are Cayley graphs of symmetric groups of permutations, with transpositions as the generating sets. A star graph is a preferred interconnection network topology to a hypercube for its ability to connect a greater number of nodes with lower degree. However, an attractive property of the hypercube is that it has a Hamiltonian decomposition, i.e. its edges can be partitioned into disjoint Hamiltonian cycles, and therefore a simple routing can be found in the case of an edge failure. The existence of Hamiltonian cycles in Cayley graphs has been known for some time. So far, there are no published results on the much stronger condition of the existence of Hamiltonian decompositions. In this paper, we give a construction of a Hamiltonian decomposition of the star graph 5-star of degree 4, by defining an automorphism for 5-star and a Hamiltonian cycle which is edge-disjoint with its image under the automorphism.

Keywords: interconnection networks, paths and cycles, graphs andgroups.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1561
1023 Using the OWA Operator in the Minkowski Distance

Authors: José M. Merigó, Anna M. Gil-Lafuente

Abstract:

We study different types of aggregation operators such as the ordered weighted averaging (OWA) operator and the generalized OWA (GOWA) operator. We analyze the use of OWA operators in the Minkowski distance. We will call these new distance aggregation operator the Minkowski ordered weighted averaging distance (MOWAD) operator. We give a general overview of this type of generalization and study some of their main properties. We also analyze a wide range of particular cases found in this generalization such as the ordered weighted averaging distance (OWAD) operator, the Euclidean ordered weighted averaging distance (EOWAD) operator, the normalized Minkowski distance, etc. Finally, we give an illustrative example of the new approach where we can see the different results obtained by using different aggregation operators.

Keywords: Aggregation operators, Minkowski distance, OWA operators, Selection of strategies.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1932
1022 The Distance between a Point and a Bezier Curveon a Bezier Surface

Authors: Wen-Haw Chen, Sheng-Gwo Chen

Abstract:

The distance between two objects is an important problem in CAGD, CAD and CG etc. It will be presented in this paper that a simple and quick method to estimate the distance between a point and a Bezier curve on a Bezier surface.

Keywords: Geodesic-like curve, distance, projection, Bezier.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2220