**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**9

# Graph Theory Related Publications

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

**Authors:**
Rajeev Saha,
Nameesh Miglani,
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

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

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

**Authors:**
Phutthiwat Waiyawuththanapoom,
Pimploi Tirastittam

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

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

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

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

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

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

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