**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**29

# Search results for: Graph theory

##### 29 An Application of Path Planning Algorithms for Autonomous Inspection of Buried Pipes with Swarm Robots

**Authors:**
Richard Molyneux,
Christopher Parrott,
Kirill Horoshenkov

**Abstract:**

This paper aims to demonstrate how various algorithms can be implemented within swarms of autonomous robots to provide continuous inspection within underground pipeline networks. Current methods of fault detection within pipes are costly, time consuming and inefficient. As such, solutions tend toward a more reactive approach, repairing faults, as opposed to proactively seeking leaks and blockages. The paper presents an efficient inspection method, showing that autonomous swarm robotics is a viable way of monitoring underground infrastructure. Tailored adaptations of various Vehicle Routing Problems (VRP) and path-planning algorithms provide a customised inspection procedure for complicated networks of underground pipes. The performance of multiple algorithms is compared to determine their effectiveness and feasibility. Notable inspirations come from ant colonies and *stigmergy*, graph theory, the k-Chinese Postman Problem ( -CPP) and traffic theory. Unlike most swarm behaviours which rely on fast communication between agents, underground pipe networks are a highly challenging communication environment with extremely limited communication ranges. This is due to the extreme variability in the pipe conditions and relatively high attenuation of acoustic and radio waves with which robots would usually communicate. This paper illustrates how to optimise the inspection process and how to increase the frequency with which the robots pass each other, without compromising the routes they are able to take to cover the whole network.

**Keywords:**
Swarm Intelligence,
Vehicle Routing Problem,
autonomous inspection,
buried pipes,
stigmergy

##### 28 2D Structured Non-Cyclic Fuzzy Graphs

**Authors:**
T. Pathinathan,
M. Peter

**Abstract:**

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

##### 27 A Graph Theoretic Approach for Quantitative Evaluation of NAAC Accreditation Criteria for the Indian University

**Authors:**
Nameesh Miglani,
Rajeev Saha,
R. S. Parihar

**Abstract:**

Estimation of the quality regarding higher education within a university is practically long drawn process besides being difficult to measure primarily due to lack of a standard scale. National Assessment and Accreditation Council (NAAC) evolved a methodology of assessment which involves self-appraisal by each university/college and an assessment of performance by an expert committee. The attributes involved in assessing a university may not be totally independent from each other thereby necessitating the consideration of interdependencies. The present study focuses on evaluation of assessment criteria using graph theoretic approach and fuzzy treatment of data collected from the students. The technique will provide a suitable platform to university management team to cross check assessment of education quality by considering interdependencies of the attributes using graph theory.

**Keywords:**
Graph Theory,
NAAC accreditation criteria,
Indian University accreditation process

##### 26 Elemental Graph Data Model: A Semantic and Topological Representation of Building Elements

**Authors:**
Yasmeen A. S. Essawy,
Khaled Nassar

**Abstract:**

With the rapid increase of complexity in the building industry, professionals in the A/E/C industry were forced to adopt Building Information Modeling (BIM) in order to enhance the communication between the different project stakeholders throughout the project life cycle and create a semantic object-oriented building model that can support geometric-topological analysis of building elements during design and construction. This paper presents a model that extracts topological relationships and geometrical properties of building elements from an existing fully designed BIM, and maps this information into a directed acyclic Elemental Graph Data Model (EGDM). The model incorporates BIM-based search algorithms for automatic deduction of geometrical data and topological relationships for each building element type. Using graph search algorithms, such as Depth First Search (DFS) and topological sortings, all possible construction sequences can be generated and compared against production and construction rules to generate an optimized construction sequence and its associated schedule. The model is implemented in a C# platform.

**Keywords:**
Building Information Modeling,
geometric and topological data models,
elemental graph data model,
and graph theory

##### 25 Selection of Material for Gear Used in Fuel Pump Using Graph Theory and Matrix Approach

**Authors:**
Sahil,
Rajeev Saha,
Sanjeev Kumar

**Abstract:**

Material selection is one of the key issues for the production of reliable and quality products in industries. A number of materials are available for a single product due to which material selection become a difficult task. The aim of this paper is to select appropriate material for gear used in fuel pump by using Graph Theory and Matrix Approach (GTMA). GTMA is a logical and systematic approach that can be used to model and analyze various engineering systems. In present work, four alternative material and their seven attributes are used to identify the best material for given product.

**Keywords:**
Decision Making,
Material,
digraph,
MADM,
GTMA

##### 24 Optimal Management of Internal Capital of Company

**Authors:**
S. Sadallah

**Abstract:**

**Keywords:**
software,
Management,
Optimal,
greedy algorithm,
graph-diagram

##### 23 Allocation of Mobile Units in an Urban Emergency Service System

**Authors:**
Dimitra Alexiou

**Abstract:**

In an urban area the location allocation of emergency services mobile units, such as ambulances, police patrol cars must be designed so as to achieve a prompt response to demand locations. In this paper the partition of a given urban network into distinct sub-networks is performed such that the vertices in each component are close and simultaneously the sums of the corresponding population in the sub-networks are almost uniform. The objective here is to position appropriately in each sub-network a mobile emergency unit in order to reduce the response time to the demands. A mathematical model in framework of graph theory is developed. In order to clarify the corresponding method a relevant numerical example is presented on a small network.

**Keywords:**
location,
Distances,
graph partition,
emergency service

##### 22 Altered Network Organization in Mild Alzheimer's Disease Compared to Mild Cognitive Impairment Using Resting-State EEG

**Authors:**
Chia-Feng Lu,
Yuh-Jen Wang,
Shin Teng,
Yu-Te Wu,
Sui-Hing Yan

**Abstract:**

Brain functional networks based on resting-state EEG data were compared between patients with mild Alzheimer’s disease (mAD) and matched patients with amnestic subtype of mild cognitive impairment (aMCI). We integrated the time–frequency cross mutual information (TFCMI) method to estimate the EEG functional connectivity between cortical regions and the network analysis based on graph theory to further investigate the alterations of functional networks in mAD compared with aMCI group. We aimed at investigating the changes of network integrity, local clustering, information processing efficiency, and fault tolerance in mAD brain networks for different frequency bands based on several topological properties, including degree, strength, clustering coefficient, shortest path length, and efficiency. Results showed that the disruptions of network integrity and reductions of network efficiency in mAD characterized by lower degree, decreased clustering coefficient, higher shortest path length, and reduced global and local efficiencies in the delta, theta, beta2, and gamma bands were evident. The significant changes in network organization can be used in assisting discrimination of mAD from aMCI in clinical.

**Keywords:**
Graph Theory,
eeg,
functional connectivity,
TFCMI

##### 21 Relations of Progression in Cognitive Decline with Initial EEG Resting-State Functional Network in Mild Cognitive Impairment

**Authors:**
Chia-Feng Lu,
Yuh-Jen Wang,
Yu-Te Wu,
Sui-Hing Yan

**Abstract:**

This study aimed at investigating whether the functional brain networks constructed using the initial EEG (obtained when patients first visited hospital) can be correlated with the progression of cognitive decline calculated as the changes of mini-mental state examination (MMSE) scores between the latest and initial examinations. We integrated the time–frequency cross mutual information (TFCMI) method to estimate the EEG functional connectivity between cortical regions, and the network analysis based on graph theory to investigate the organization of functional networks in aMCI. Our finding suggested that higher integrated functional network with sufficient connection strengths, dense connection between local regions, and high network efficiency in processing information at the initial stage may result in a better prognosis of the subsequent cognitive functions for aMCI. In conclusion, the functional connectivity can be a useful biomarker to assist in prediction of cognitive declines in aMCI.

**Keywords:**
Cognitive Decline,
functional connectivity,
MCI,
MMSE

##### 20 On Chromaticity of Wheels

**Authors:**
Zainab Yasir Al-Rekaby,
Abdul Jalil M. Khalaf

**Abstract:**

Let the vertices of a graph such that every two adjacent vertices have different color is a very common problem in the graph theory. This is known as proper coloring of graphs. The possible number of different proper colorings on a graph with a given number of colors can be represented by a function called the chromatic polynomial. Two graphs G and H are said to be chromatically equivalent, if they share the same chromatic polynomial. A Graph G is chromatically unique, if G is isomorphic to H for any graph H such that G is chromatically equivalent to H. The study of chromatically equivalent and chromatically unique problems is called chromaticity. This paper shows that a wheel W12 is chromatically unique.

**Keywords:**
chromatic polynomial,
chromatically equivalent,
chromatically unique,
wheel

##### 19 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

##### 18 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

##### 17 Public Transport Planning System by Dijkstra Algorithm: Case Study Bangkok Metropolitan Area

**Authors:**
Pimploi Tirastittam,
Phutthiwat Waiyawuththanapoom

**Abstract:**

Nowadays the promotion of the public transportation system in the Bangkok Metropolitan Area is increased such as the “Free Bus for Thai Citizen” Campaign and the prospect of the several MRT routes to increase the convenient and comfortable to the Bangkok Metropolitan area citizens. But citizens do not make full use of them it because the citizens are lack of the data and information and also the confident to the public transportation system of Thailand especially in the time and safety aspects. This research is the Public Transport Planning System by Dijkstra Algorithm: Case Study Bangkok Metropolitan Area by focusing on buses, BTS and MRT schedules/routes to give the most information to passengers. They can choose the way and the routes easily by using Dijkstra STAR Algorithm of Graph Theory which also shows the fare of the trip. This Application was evaluated by 30 normal users to find the mean and standard deviation of the developed system. Results of the evaluation showed that system is at a good level of satisfaction (4.20 and 0.40). From these results we can conclude that the system can be used properly and effectively according to the objective.

**Keywords:**
Graph Theory,
public transport,
Dijkstra algorithm,
Bangkok metropolitan area,
Shortest Route

##### 16 A Comprehensive model for developing of Steer-By-Wire System

**Authors:**
Reza Kazemi ,
Iman Mousavinejad

**Abstract:**

Steer-By-Wire ( SBW ) has several advantages of packaging flexibility , advanced vehicle control system ,and superior performance . SBW has no mechanical linkage between the steering gear and the steering column. It is possible to control the steering wheel and the front-wheel steering independently. SBW system is composed of two motors controlled by ECU. One motor in the steering wheel is to improve the driver's steering feel and the other motor in the steering linkage is to improve the vehicle maneuverability and stability. This paper shows a new approach at modeling of SBW system by Bond Graph theory. The mechanical parts , the steering wheel motor and the front wheel motor will be modeled by this theory. The work in the paper will help to guide further researches on control algorithm of the SBW system .

**Keywords:**
Modeling,
Steer-By-Wire ( SBW ),
Bond Graph theory,
Electronic-Control-Unit ( ECU )

##### 15 A New Integer Programming Formulation for the Chinese Postman Problem with Time Dependent Travel Times

**Authors:**
Jinghao Sun,
Guozhen Tan,
Guangjian Hou

**Abstract:**

**Keywords:**
Integer Programming,
time dependent,
upper bound analysis,
Chinese Postman Problem

##### 14 A Finite-Time Consensus Protocol of the Multi-Agent Systems

**Authors:**
Xin-Lei Feng,
Ting-Zhu Huang

**Abstract:**

According to conjugate gradient algorithm, a new consensus protocol algorithm of discrete-time multi-agent systems is presented, which can achieve finite-time consensus. Finally, a numerical example is given to illustrate our theoretical result.

**Keywords:**
Multi-Agent Systems,
Graph Theory,
Conjugate Gradient algorithm,
Consensus protocols,
Finite-time

##### 13 Distributed Load Flow Analysis using Graph Theory

**Authors:**
D. P. Sharma,
A. Chaturvedi,
G.Purohit ,
R.Shivarudraswamy

**Abstract:**

**Keywords:**
graph,
array,
radial distribution network,
Load-flow

##### 12 Evaluating the Innovation Ability of Manufacturing Resources

**Authors:**
M.F. Zaeh,
G. Reinhart,
U. Lindemann,
F. Karl,
W. Biedermann

**Abstract:**

Due to today-s turbulent environment, manufacturing resources, particularly in assembly, must be reconfigured frequently. These reconfigurations are caused by various, partly cyclic, influencing factors. Hence, it is important to evaluate the innovation ability - the capability of resources to implement innovations quickly and efficiently without large expense - of manufacturing resources. For this purpose, a new methodology is presented in this article. Within the methodology, design structure matrices and graph theory are used. The results of the methodology include different indices to evaluate the innovation ability of the manufacturing resources. Due to the cyclicity of the influencing factors, the methodology can be used to synchronize the realization of adaptations.

**Keywords:**
Production Management,
Graph Theory,
Manufacturing Resource Planning,
Changeability,
Cycle Management,
Design StructureMatrices

##### 11 Modeling And Analysis of Simple Open Cycle Gas Turbine Using Graph Networks

**Authors:**
Naresh Yadav,
I.A. Khan,
Sandeep Grover

**Abstract:**

**Keywords:**
Simple open cycle gas turbine,
Graph theoretic approach,
process subgraphs,
gas turbines system modeling,
systemtheory

##### 10 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

##### 9 Detecting Community Structure in Amino Acid Interaction Networks

**Authors:**
Omar GACI,
Stefan BALEV,
Antoine DUTOT

**Abstract:**

In this paper we introduce the notion of protein interaction network. This is a graph whose vertices are the protein-s amino acids and whose edges are the interactions between them. Using a graph theory approach, we observe that according to their structural roles, the nodes interact differently. By leading a community structure detection, we confirm this specific behavior and describe thecommunities composition to finally propose a new approach to fold a protein interaction network.

**Keywords:**
protein structure,
interaction network,
community structure detection

##### 8 A New Distribution Network Reconfiguration Approach using a Tree Model

**Authors:**
E. Dolatdar,
S. Soleymani,
B. Mozafari

**Abstract:**

Power loss reduction is one of the main targets in power industry and so in this paper, the problem of finding the optimal configuration of a radial distribution system for loss reduction is considered. Optimal reconfiguration involves the selection of the best set of branches to be opened ,one each from each loop, for reducing resistive line losses , and reliving overloads on feeders by shifting the load to adjacent feeders. However ,since there are many candidate switching combinations in the system ,the feeder reconfiguration is a complicated problem. In this paper a new approach is proposed based on a simple optimum loss calculation by determining optimal trees of the given network. From graph theory a distribution network can be represented with a graph that consists a set of nodes and branches. In fact this problem can be viewed as a problem of determining an optimal tree of the graph which simultaneously ensure radial structure of each candidate topology .In this method the refined genetic algorithm is also set up and some improvements of algorithm are made on chromosome coding. In this paper an implementation of the algorithm presented by [7] is applied by modifying in load flow program and a comparison of this method with the proposed method is employed. In [7] an algorithm is proposed that the choice of the switches to be opened is based on simple heuristic rules. This algorithm reduce the number of load flow runs and also reduce the switching combinations to a fewer number and gives the optimum solution. To demonstrate the validity of these methods computer simulations with PSAT and MATLAB programs are carried out on 33-bus test system. The results show that the performance of the proposed method is better than [7] method and also other methods.

**Keywords:**
Optimization,
Graph Theory,
Genetic Algorithm,
Distribution System,
loss reduction,
reconfiguration

##### 7 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:**

**Keywords:**
eigenvalues,
M-Tree,
graph database,
protein
structure,
spectra graph theory

##### 6 PoPCoRN: A Power-Aware Periodic Surveillance Scheme in Convex Region using Wireless Mobile Sensor Networks

**Authors:**
A. K. Prajapati

**Abstract:**

**Keywords:**
Communication,
Sensor Network,
Graph Theory,
MSN

##### 5 Automatic Fingerprint Classification Using Graph Theory

**Authors:**
Mana Tarjoman,
Shaghayegh Zarei

**Abstract:**

Using efficient classification methods is necessary for automatic fingerprint recognition system. This paper introduces a new structural approach to fingerprint classification by using the directional image of fingerprints to increase the number of subclasses. In this method, the directional image of fingerprints is segmented into regions consisting of pixels with the same direction. Afterwards the relational graph to the segmented image is constructed and according to it, the super graph including prominent information of this graph is formed. Ultimately we apply a matching technique to compare obtained graph with the model graphs in order to classify fingerprints by using cost function. Increasing the number of subclasses with acceptable accuracy in classification and faster processing in fingerprints recognition, makes this system superior.

**Keywords:**
Fingerprint,
classification,
graph,
Directional image,
Super graph

##### 4 Another Formal Proposal For Stealth

**Authors:**
Adrien Derock,
Pascal Veron

**Abstract:**

**Keywords:**
Detection,
graph,
eradication,
stealth,
rootkit

##### 3 A General Model for Amino Acid Interaction Networks

**Authors:**
Omar Gaci,
Stefan Balev

**Abstract:**

**Keywords:**
protein structure,
small-world network,
interaction network

##### 2 Using Multi-Thread Technology Realize Most Short-Path Parallel Algorithm

**Authors:**
Chang-le Lu,
Yong Chen

**Abstract:**

**Keywords:**
Parallel Algorithms,
Dijkstra algorithm,
ratio,
multi-thread
technology,
most short-path

##### 1 Automating the Testing of Object Behaviour: A Statechart-Driven Approach

**Authors:**
Dong He Nam,
Eric C. Mousset,
David C. Levy

**Abstract:**

The evolution of current modeling specifications gives rise to the problem of generating automated test cases from a variety of application tools. Past endeavours on behavioural testing of UML statecharts have not systematically leveraged the potential of existing graph theory for testing of objects. Therefore there exists a need for a simple, tool-independent, and effective method for automatic test generation. An architecture, codenamed ACUTE-J (Automated stateChart Unit Testing Engine for Java), for automating the unit test generation process is presented. A sequential approach for converting UML statechart diagrams to JUnit test classes is described, with the application of existing graph theory. Research byproducts such as a universal XML Schema and API for statechart-driven testing are also proposed. The result from a Java implementation of ACUTE-J is discussed in brief. The Chinese Postman algorithm is utilised as an illustration for a run-through of the ACUTE-J architecture.

**Keywords:**
UML,
model based testing,
automated testing,
Unit Testing,
statechart
testing