**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**1218

# Search results for: minimum spanning tree.

##### 1218 Spanning Tree Transformation of Connected Graphs into Single-Row Networks

**Authors:**
S.L. Loh,
S. Salleh,
N.H. Sarmin

**Abstract:**

**Keywords:**
Graph theory,
simulated annealing,
single-rowrouting and spanning tree.

##### 1217 Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbour and Minimum Spanning Tree Algorithms

**Authors:**
Fatma A. Karkory,
Ali A. Abudalmola

**Abstract:**

The travelling salesman problem (TSP) is a combinatorial optimization problem in which the goal is to find the shortest path between different cities that the salesman takes. In other words, the problem deals with finding a route covering all cities so that total distance and execution time is minimized. This paper adopts the nearest neighbor and minimum spanning tree algorithm to solve the well-known travelling salesman problem. The algorithms were implemented using java programming language. The approach is tested on three graphs that making a TSP tour instance of 5-city, 10 –city, and 229–city. The computation results validate the performance of the proposed algorithm.

**Keywords:**
Heuristics,
minimum spanning tree algorithm,
Nearest Neighbor,
Travelling Salesman Problem (TSP).

##### 1216 A Minimum Spanning Tree-Based Method for Initializing the K-Means Clustering Algorithm

**Authors:**
J. Yang,
Y. Ma,
X. Zhang,
S. Li,
Y. Zhang

**Abstract:**

The traditional k-means algorithm has been widely used as a simple and efficient clustering method. However, the algorithm often converges to local minima for the reason that it is sensitive to the initial cluster centers. In this paper, an algorithm for selecting initial cluster centers on the basis of minimum spanning tree (MST) is presented. The set of vertices in MST with same degree are regarded as a whole which is used to find the skeleton data points. Furthermore, a distance measure between the skeleton data points with consideration of degree and Euclidean distance is presented. Finally, MST-based initialization method for the k-means algorithm is presented, and the corresponding time complexity is analyzed as well. The presented algorithm is tested on five data sets from the UCI Machine Learning Repository. The experimental results illustrate the effectiveness of the presented algorithm compared to three existing initialization methods.

**Keywords:**
Degree,
initial cluster center,
k-means,
minimum spanning tree.

##### 1215 Geometric Data Structures and Their Selected Applications

**Authors:**
Miloš Šeda

**Abstract:**

**Keywords:**
motion planning,
spanning tree,
Steiner tree,
Delaunay triangulation,
Voronoi diagram.

##### 1214 Applying Spanning Tree Graph Theory for Automatic Database Normalization

**Authors:**
Chetneti Srisa-an

**Abstract:**

In Knowledge and Data Engineering field, relational database is the best repository to store data in a real world. It has been using around the world more than eight decades. Normalization is the most important process for the analysis and design of relational databases. It aims at creating a set of relational tables with minimum data redundancy that preserve consistency and facilitate correct insertion, deletion, and modification. Normalization is a major task in the design of relational databases. Despite its importance, very few algorithms have been developed to be used in the design of commercial automatic normalization tools. It is also rare technique to do it automatically rather manually. Moreover, for a large and complex database as of now, it make even harder to do it manually. This paper presents a new complete automated relational database normalization method. It produces the directed graph and spanning tree, first. It then proceeds with generating the 2NF, 3NF and also BCNF normal forms. The benefit of this new algorithm is that it can cope with a large set of complex function dependencies.

**Keywords:**
Relational Database,
Functional Dependency,
Automatic Normalization,
Primary Key,
Spanning tree.

##### 1213 A Spanning Tree for Enhanced Cluster Based Routing in Wireless Sensor Network

**Authors:**
M. Saravanan,
M. Madheswaran

**Abstract:**

Wireless Sensor Network (WSN) clustering architecture enables features like network scalability, communication overhead reduction, and fault tolerance. After clustering, aggregated data is transferred to data sink and reducing unnecessary, redundant data transfer. It reduces nodes transmitting, and so saves energy consumption. Also, it allows scalability for many nodes, reduces communication overhead, and allows efficient use of WSN resources. Clustering based routing methods manage network energy consumption efficiently. Building spanning trees for data collection rooted at a sink node is a fundamental data aggregation method in sensor networks. The problem of determining Cluster Head (CH) optimal number is an NP-Hard problem. In this paper, we combine cluster based routing features for cluster formation and CH selection and use Minimum Spanning Tree (MST) for intra-cluster communication. The proposed method is based on optimizing MST using Simulated Annealing (SA). In this work, normalized values of mobility, delay, and remaining energy are considered for finding optimal MST. Simulation results demonstrate the effectiveness of the proposed method in improving the packet delivery ratio and reducing the end to end delay.

**Keywords:**
Wireless sensor network,
clustering,
minimum spanning tree,
genetic algorithm,
low energy adaptive clustering hierarchy,
simulated annealing.

##### 1212 Clustering in WSN Based on Minimum Spanning Tree Using Divide and Conquer Approach

**Authors:**
Uttam Vijay,
Nitin Gupta

**Abstract:**

Due to heavy energy constraints in WSNs clustering is an efficient way to manage the energy in sensors. There are many methods already proposed in the area of clustering and research is still going on to make clustering more energy efficient. In our paper we are proposing a minimum spanning tree based clustering using divide and conquer approach. The MST based clustering was first proposed in 1970’s for large databases. Here we are taking divide and conquer approach and implementing it for wireless sensor networks with the constraints attached to the sensor networks. This Divide and conquer approach is implemented in a way that we don’t have to construct the whole MST before clustering but we just find the edge which will be the part of the MST to a corresponding graph and divide the graph in clusters there itself if that edge from the graph can be removed judging on certain constraints and hence saving lot of computation.

**Keywords:**
Algorithm,
Clustering,
Edge-Weighted Graph,
Weighted-LEACH.

##### 1211 A Preemptive Link State Spanning Tree Source Routing Scheme for Opportunistic Data Forwarding in MANET

**Authors:**
R. Poonkuzhali,
M. Y. Sanavullah,
A. Sabari

**Abstract:**

Opportunistic Data Forwarding (ODF) has drawn much attention in mobile adhoc networking research in recent years. The effectiveness of ODF in MANET depends on a suitable routing protocol which provides a powerful source routing services. PLSR is featured by source routing, loop free and small routing overhead. The update messages in PLSR are integrated into a tree structure and no need to time stamp routing updates which reduces the routing overhead.

**Keywords:**
Mobile ad hoc network (MANET),
Opportunistic data forwarding (ODF),
Preemptive link state spanning tree routing (PLSR),
Depth First Search (DFS).

##### 1210 Independent Spanning Trees on Systems-on-chip Hypercubes Routing

**Authors:**
Eduardo Sant'Ana da Silva,
Andre Luiz Pires Guedes,
Eduardo Todt

**Abstract:**

Independent spanning trees (ISTs) provide a number of advantages in data broadcasting. One can cite the use in fault tolerance network protocols for distributed computing and bandwidth. However, the problem of constructing multiple ISTs is considered hard for arbitrary graphs. In this paper we present an efficient algorithm to construct ISTs on hypercubes that requires minimum resources to be performed.

**Keywords:**
Hypercube,
Independent Spanning Trees,
Networks
On Chip,
Systems On Chip.

##### 1209 Minimal Spanning Tree based Fuzzy Clustering

**Authors:**
Ágnes Vathy-Fogarassy,
Balázs Feil,
János Abonyi

**Abstract:**

**Keywords:**
Clustering,
fuzzy clustering,
minimal spanning tree,
cluster validity,
fuzzy similarity.

##### 1208 N-Sun Decomposition of Complete Graphs and Complete Bipartite Graphs

**Authors:**
R. Anitha,
R. S. Lekshmi

**Abstract:**

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

##### 1207 Consensus of Multi-Agent Systems under the Special Consensus Protocols

**Authors:**
Konghe Xie

**Abstract:**

**Keywords:**
Consensus,
multi-agent systems,
directed spanning
tree,
the Laplacian matrix.

##### 1206 A Methodology for Definition of Road Networks in Rural Areas of Nepal

**Authors:**
J. K. Shrestha,
A. Benta,
R. B. Lopes,
N. Lopes

**Abstract:**

**Keywords:**
Minimum spanning tree,
nodal points,
rural road network.

##### 1205 Distributed 2-Vertex Connectivity Test of Graphs Using Local Knowledge

**Authors:**
Brahim Hamid,
Bertrand Le Saec,
Mohamed Mosbah

**Abstract:**

The vertex connectivity of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. This work is devoted to the problem of vertex connectivity test of graphs in a distributed environment based on a general and a constructive approach. The contribution of this paper is threefold. First, using a preconstructed spanning tree of the considered graph, we present a protocol to test whether a given graph is 2-connected using only local knowledge. Second, we present an encoding of this protocol using graph relabeling systems. The last contribution is the implementation of this protocol in the message passing model. For a given graph G, where M is the number of its edges, N the number of its nodes and Δ is its degree, our algorithms need the following requirements: The first one uses O(Δ×N2) steps and O(Δ×logΔ) bits per node. The second one uses O(Δ×N2) messages, O(N2) time and O(Δ × logΔ) bits per node. Furthermore, the studied network is semi-anonymous: Only the root of the pre-constructed spanning tree needs to be identified.

**Keywords:**
Distributed computing,
fault-tolerance,
graph relabeling systems,
local computations,
local knowledge,
message passing system,
networks,
vertex connectivity.

##### 1204 Auto Regressive Tree Modeling for Parametric Optimization in Fuzzy Logic Control System

**Authors:**
Arshia Azam,
J. Amarnath,
Ch. D. V. Paradesi Rao

**Abstract:**

**Keywords:**
Fuzzy logic,
branch T-S fuzzy model,
tree modeling,
complex nonlinear system.

##### 1203 Construction Of Decentralized Lifetime Maximizing Tree for Data Aggregation in Wireless Sensor Networks

**Authors:**
Deepali Virmani ,
Satbir Jain

**Abstract:**

**Keywords:**
branch energy,
decentralized,
energy level ,
lifetime,
tree energy,
wireless sensor networks.

##### 1202 Revised PLWAP Tree with Non-frequent Items for Mining Sequential Pattern

**Authors:**
R. Vishnu Priya,
A. Vadivel

**Abstract:**

Sequential pattern mining is a challenging task in data mining area with large applications. One among those applications is mining patterns from weblog. Recent times, weblog is highly dynamic and some of them may become absolute over time. In addition, users may frequently change the threshold value during the data mining process until acquiring required output or mining interesting rules. Some of the recently proposed algorithms for mining weblog, build the tree with two scans and always consume large time and space. In this paper, we build Revised PLWAP with Non-frequent Items (RePLNI-tree) with single scan for all items. While mining sequential patterns, the links related to the nonfrequent items are not considered. Hence, it is not required to delete or maintain the information of nodes while revising the tree for mining updated transactions. The algorithm supports both incremental and interactive mining. It is not required to re-compute the patterns each time, while weblog is updated or minimum support changed. The performance of the proposed tree is better, even the size of incremental database is more than 50% of existing one. For evaluation purpose, we have used the benchmark weblog dataset and found that the performance of proposed tree is encouraging compared to some of the recently proposed approaches.

**Keywords:**
Sequential pattern mining,
weblog,
frequent and non-frequent items,
incremental and interactive mining.

##### 1201 Balancing of Quad Tree using Point Pattern Analysis

**Authors:**
Amitava Chakraborty,
Sudip Kumar De,
Ranjan Dasgupta

**Abstract:**

**Keywords:**
Algorithm,
Height balanced tree,
Point patternanalysis,
Point quad tree.

##### 1200 An Attribute-Centre Based Decision Tree Classification Algorithm

**Authors:**
Gökhan Silahtaroğlu

**Abstract:**

**Keywords:**
Classification,
decision tree,
split,
pruning,
entropy,
gini.

##### 1199 Some New Bounds for a Real Power of the Normalized Laplacian Eigenvalues

**Authors:**
Ayşe Dilek Maden

**Abstract:**

For a given a simple connected graph, we present some new bounds via a new approach for a special topological index given by the sum of the real number power of the non-zero normalized Laplacian eigenvalues. To use this approach presents an advantage not only to derive old and new bounds on this topic but also gives an idea how some previous results in similar area can be developed.

**Keywords:**
Degree Kirchhoff index,
normalized Laplacian
eigenvalue,
spanning tree.

##### 1198 Improving Fault Resilience and Reconstruction of Overlay Multicast Tree Using Leaving Time of Participants

**Authors:**
Bhed Bahadur Bista

**Abstract:**

**Keywords:**
Network layer multicast,
Fault Resilience,
IP multicast

##### 1197 The Mutated Distance between Two Mixture Trees

**Authors:**
Wan Chian Li,
Justie Su-Tzu Juan,
Yi-Chun Wang,
Shu-Chuan Chen

**Abstract:**

The evolutionary tree is an important topic in bioinformation. In 2006, Chen and Lindsay proposed a new method to build the mixture tree from DNA sequences. Mixture tree is a new type evolutionary tree, and it has two additional information besides the information of ordinary evolutionary tree. One of the information is time parameter, and the other is the set of mutated sites. In 2008, Lin and Juan proposed an algorithm to compute the distance between two mixture trees. Their algorithm computes the distance with only considering the time parameter between two mixture trees. In this paper, we proposes a method to measure the similarity of two mixture trees with considering the set of mutated sites and develops two algorithm to compute the distance between two mixture trees. The time complexity of these two proposed algorithms are O(n2 × max{h(T1), h(T2)}) and O(n2), respectively

**Keywords:**
evolutionary tree,
mixture tree,
mutated site,
distance.

##### 1196 Improved C-Fuzzy Decision Tree for Intrusion Detection

**Authors:**
Krishnamoorthi Makkithaya,
N. V. Subba Reddy,
U. Dinesh Acharya

**Abstract:**

**Keywords:**
Data mining,
Decision tree,
Feature selection,
Fuzzyc- means clustering,
Intrusion detection.

##### 1195 Visualising Energy Efficiency Landscape

**Authors:**
Hairulliza M. Judi,
Soon Y. Chee

**Abstract:**

**Keywords:**
Tree planting,
tree shading,
energy efficiency,
visualization.

##### 1194 Combining Minimum Energy and Minimum Direct Jerk of Linear Dynamic Systems

**Authors:**
V. Tawiwat,
P. Jumnong

**Abstract:**

**Keywords:**
Optimization,
Dynamic,
Linear Systems,
Jerks.

##### 1193 [a, b]-Factors Excluding Some Specified Edges In Graphs

**Authors:**
Sizhong Zhou,
Bingyuan Pu

**Abstract:**

Let G be a graph of order n, and let a, b and m be positive integers with 1 ≤ a<b. An [a, b]-factor of G is deﬁned as a spanning subgraph F of G such that a ≤ dF (x) ≤ b for each x ∈ V (G). In this paper, it is proved that if n ≥ (a+b−1+√(a+b+1)m−2)2−1 b and δ(G) > n + a + b − 2 √bn+ 1, then for any subgraph H of G with m edges, G has an [a, b]-factor F such that E(H)∩ E(F) = ∅. This result is an extension of thatof Egawa [2].

**Keywords:**
graph,
minimum degree,
[a,
b]-factor.

##### 1192 On Minimum Cycle Bases of the Wreath Product of Wheels with Stars

**Authors:**
M. M. M. Jaradat,
M. K. Al-Qeyyam

**Abstract:**

The length of a cycle basis of a graph is the sum of the lengths of its elements. A minimum cycle basis is a cycle basis with minimum length. In this work, a construction of a minimum cycle basis for the wreath product of wheels with stars is presented. Moreover, the length of minimum cycle basis and the length of its longest cycle are calculated.

**Keywords:**
Cycle space,
minimum cycle basis,
wreath product.

##### 1191 Dynamic Routing to Multiple Destinations in IP Networks using Hybrid Genetic Algorithm (DRHGA)

**Authors:**
K. Vijayalakshmi,
S. Radhakrishnan

**Abstract:**

In this paper we have proposed a novel dynamic least cost multicast routing protocol using hybrid genetic algorithm for IP networks. Our protocol finds the multicast tree with minimum cost subject to delay, degree, and bandwidth constraints. The proposed protocol has the following features: i. Heuristic local search function has been devised and embedded with normal genetic operation to increase the speed and to get the optimized tree, ii. It is efficient to handle the dynamic situation arises due to either change in the multicast group membership or node / link failure, iii. Two different crossover and mutation probabilities have been used for maintaining the diversity of solution and quick convergence. The simulation results have shown that our proposed protocol generates dynamic multicast tree with lower cost. Results have also shown that the proposed algorithm has better convergence rate, better dynamic request success rate and less execution time than other existing algorithms. Effects of degree and delay constraints have also been analyzed for the multicast tree interns of search success rate.

**Keywords:**
Dynamic Group membership change,
Hybrid Genetic Algorithm,
Link / node failure,
QoS Parameters.

##### 1190 The Leaves of a Tree

**Authors:**
Zhu Jiaming,
Yu Mengna

**Abstract:**

**Keywords:**
Leaf shape; Mass; Fuzzy cluster; Regression analysis;
Eviews; Matlab

##### 1189 Balancing Neural Trees to Improve Classification Performance

**Authors:**
Asha Rani,
Christian Micheloni,
Gian Luca Foresti

**Abstract:**

**Keywords:**
Neural Tree,
Pattern Classification,
Perceptron,
Splitting
Nodes.