**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**8882

# Search results for: data flow graph

##### 8882 Efficient Filtering of Graph Based Data Using Graph Partitioning

**Authors:**
Nileshkumar Vaishnav,
Aditya Tatu

**Abstract:**

**Keywords:**
Graph signal processing,
graph partitioning,
inverse
filtering on graphs,
algebraic signal processing.

##### 8881 Computing the Loop Bound in Iterative Data Flow Graphs Using Natural Token Flow

**Authors:**
Ali Shatnawi

**Abstract:**

**Keywords:**
Data flow graph,
Iteration period bound,
Rateoptimalscheduling,
Recursive DSP algorithms.

##### 8880 AJcFgraph - AspectJ Control Flow Graph Builder for Aspect-Oriented Software

**Authors:**
Reza Meimandi Parizi,
Abdul Azim Abdul Ghani

**Abstract:**

**Keywords:**
Aspect-Oriented Software Development,
AspectJ,
Control Flow Graph,
Data Flow Analysis

##### 8879 Topological Queries on Graph-structured XML Data: Models and Implementations

**Authors:**
Hongzhi Wang,
Jianzhong Li,
Jizhou Luo

**Abstract:**

**Keywords:**
XML,
Graph Structure,
Topological query.

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

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

**Abstract:**

**Keywords:**
Radial Distribution network,
Graph,
Load-flow,
Array.

##### 8877 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.

##### 8876 GRCNN: Graph Recognition Convolutional Neural Network for Synthesizing Programs from Flow Charts

**Authors:**
Lin Cheng,
Zijiang Yang

**Abstract:**

**Keywords:**
program synthesis,
flow chart,
specification,
graph
recognition,
CNN.

##### 8875 An Efficient Graph Query Algorithm Based on Important Vertices and Decision Features

**Authors:**
Xiantong Li,
Jianzhong Li

**Abstract:**

**Keywords:**
Decision Feature,
Frequent Feature,
Graph Dataset,
Graph Query

##### 8874 Speedup Breadth-First Search by Graph Ordering

**Abstract:**

Breadth-First Search (BFS) is a core graph algorithm that is widely used for graph analysis. As it is frequently used in many graph applications, improving the BFS performance is essential. In this paper, we present a graph ordering method that could reorder the graph nodes to achieve better data locality, thus, improving the BFS performance. Our method is based on an observation that the sibling relationships will dominate the cache access pattern during the BFS traversal. Therefore, we propose a frequency-based model to construct the graph order. First, we optimize the graph order according to the nodes’ visit frequency. Nodes with high visit frequency will be processed in priority. Second, we try to maximize the child nodes’ overlap layer by layer. As it is proved to be NP-hard, we propose a heuristic method that could greatly reduce the preprocessing overheads.We conduct extensive experiments on 16 real-world datasets. The result shows that our method could achieve comparable performance with the state-of-the-art methods while the graph ordering overheads are only about 1/15.

**Keywords:**
Breadth-first search,
BFS,
graph ordering,
graph algorithm.

##### 8873 Concurrency in Web Access Patterns Mining

**Authors:**
Jing Lu,
Malcolm Keech,
Weiru Chen

**Abstract:**

**Keywords:**
concurrent access patterns (CAP),
CAP mining and modelling,
CAP-Graph,
web access patterns (WAP),
WAP-Graph,
Web usage mining.

##### 8872 A Neighborhood Condition for Fractional k-deleted Graphs

**Authors:**
Sizhong Zhou,
Hongxia Liu

**Abstract:**

Abstract–Let k ≥ 3 be an integer, and let G be a graph of order n with n ≥ 9k +3- 42(k - 1)2 + 2. Then a spanning subgraph F of G is called a k-factor if dF (x) = k for each x ∈ V (G). A fractional k-factor is a way of assigning weights to the edges of a graph G (with all weights between 0 and 1) such that for each vertex the sum of the weights of the edges incident with that vertex is k. A graph G is a fractional k-deleted graph if there exists a fractional k-factor after deleting any edge of G. In this paper, it is proved that G is a fractional k-deleted graph if G satisfies δ(G) ≥ k + 1 and |NG(x) ∪ NG(y)| ≥ 1 2 (n + k - 2) for each pair of nonadjacent vertices x, y of G.

**Keywords:**
Graph,
minimum degree,
neighborhood union,
fractional k-factor,
fractional k-deleted graph.

##### 8871 Data and Control Flow Analysis of VDMµ Specifications

**Authors:**
Mubina Nazmeen,
Iram Rubab

**Abstract:**

**Keywords:**
VDM-SL,
VDMµ,
data flow graph,
control flowgraph,
testing,
formal specification.

##### 8870 The Extremal Graph with the Largest Merrifield-Simmons Index of (n, n + 2)-graphs

**Authors:**
M. S. Haghighat,
A. Dolati,
M. Tabari,
E. Mohseni

**Abstract:**

The Merrifield-Simmons index of a graph G is defined as the total number of its independent sets. A (n, n + 2)-graph is a connected simple graph with n vertices and n + 2 edges. In this paper we characterize the (n, n+2)-graph with the largest Merrifield- Simmons index. We show that its Merrifield-Simmons index i.e. the upper bound of the Merrifield-Simmons index of the (n, n+2)-graphs is 9 × 2n-5 +1 for n ≥ 5.

**Keywords:**
Merrifield-Simmons index,
(n,
n+2)-graph.

##### 8869 N-Sun Decomposition of Complete, Complete Bipartite and Some Harary Graphs

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

**Abstract:**

**Keywords:**
Decomposition,
Hamilton cycle,
n-sun graph,
perfect matching,
spanning tree.

##### 8868 Connected Vertex Cover in 2-Connected Planar Graph with Maximum Degree 4 is NP-complete

**Authors:**
Priyadarsini P. L. K,
Hemalatha T.

**Abstract:**

**Keywords:**
NP-complete,
2-Connected planar graph,
block,
cut vertex

##### 8867 The Diameter of an Interval Graph is Twice of its Radius

**Authors:**
Tarasankar Pramanik,
Sukumar Mondal,
Madhumangal Pal

**Abstract:**

In an interval graph G = (V,E) the distance between two vertices u, v is de£ned as the smallest number of edges in a path joining u and v. The eccentricity of a vertex v is the maximum among distances from all other vertices of V . The diameter (δ) and radius (ρ) of the graph G is respectively the maximum and minimum among all the eccentricities of G. The center of the graph G is the set C(G) of vertices with eccentricity ρ. In this context our aim is to establish the relation ρ = δ 2 for an interval graph and to determine the center of it.

**Keywords:**
Interval graph,
interval tree,
radius,
center.

##### 8866 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,
elemental graph data model,
geometric and topological data models,
and graph theory.

##### 8865 Completion Number of a Graph

**Authors:**
Sudhakar G

**Abstract:**

In this paper a new concept of partial complement of a graph G is introduced and using the same a new graph parameter, called completion number of a graph G, denoted by c(G) is defined. Some basic properties of graph parameter, completion number, are studied and upperbounds for completion number of classes of graphs are obtained , the paper includes the characterization also.

**Keywords:**
Completion Number,
Maximum Independent subset,
Partial complements,
Partial self complementary

##### 8864 Estimating the Flow Velocity Using Flow Generated Sound

**Authors:**
Saeed Hosseini,
Ali Reza Tahavvor

**Abstract:**

**Keywords:**
Flow generated sound,
sound processing,
speed,
wave power.

##### 8863 On Fractional (k,m)-Deleted Graphs with Constrains Conditions

**Authors:**
Sizhong Zhou,
Hongxia Liu

**Abstract:**

Let G be a graph of order n, and let k 2 and m 0 be two integers. Let h : E(G) [0, 1] be a function. If e∋x h(e) = k holds for each x V (G), then we call G[Fh] a fractional k-factor of G with indicator function h where Fh = {e E(G) : h(e) > 0}. A graph G is called a fractional (k,m)-deleted graph if there exists a fractional k-factor G[Fh] of G with indicator function h such that h(e) = 0 for any e E(H), where H is any subgraph of G with m edges. In this paper, it is proved that G is a fractional (k,m)-deleted graph if (G) k + m + m k+1 , n 4k2 + 2k − 6 + (4k 2 +6k−2)m−2 k−1 and max{dG(x), dG(y)} n 2 for any vertices x and y of G with dG(x, y) = 2. Furthermore, it is shown that the result in this paper is best possible in some sense.

**Keywords:**
Graph,
degree condition,
fractional k-factor,
fractional (k,
m)-deleted graph.

##### 8862 Face Recognition using a Kernelization of Graph Embedding

**Authors:**
Pang Ying Han,
Hiew Fu San,
Ooi Shih Yin

**Abstract:**

**Keywords:**
Face recognition,
Fisher discriminant,
graph
embedding,
kernelization.

##### 8861 Metric Dimension on Line Graph of Honeycomb Networks

**Authors:**
M. Hussain,
Aqsa Farooq

**Abstract:**

**Keywords:**
Resolving set,
metric dimension,
honeycomb network,
line graph.

##### 8860 Comparison of Full Graph Methods of Switched Circuits Solution

**Authors:**
Zdeňka Dostálová,
David Matoušek,
Bohumil Brtnik

**Abstract:**

**Keywords:**
Switched capacitors of two phases,
switched
currents of two phases,
transformation graph,
two-graph,
Mason's
formula,
voltage transfer,
summary graph.

##### 8859 Reductions of Control Flow Graphs

**Authors:**
Robert Gold

**Abstract:**

Control ﬂow graphs are a well-known representation of the sequential control ﬂow 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 ﬂow graphs. In this case the size of the graphs can grow considerably and thus makes it difﬁcult for software engineers to analyze the control ﬂow. Graph reductions are helpful in this situation. In this paper we deﬁne reductions to subsets of nodes. Since executions of programs are represented by paths through the control ﬂow graphs, paths should be preserved. Furthermore, the composition of reductions makes a stepwise analysis approach possible.

**Keywords:**
Control ﬂow graph,
graph reduction.

##### 8858 On Detour Spectra of Some Graphs

**Authors:**
S.K.Ayyaswamy,
S.Balachandran

**Abstract:**

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

##### 8857 File Format of Flow Chart Simulation Software - CFlow

**Authors:**
Syahanim Mohd Salleh,
Zaihosnita Hood,
Hairulliza Mohd Judi,
Marini Abu Bakar

**Abstract:**

**Keywords:**
CFlow,
flow chart,
file format.

##### 8856 SIMGraph: Simplifying Contig Graph to Improve de Novo Genome Assembly Using Next-generation Sequencing Data

**Authors:**
Chien-Ju Li,
Chun-Hui Yu,
Chi-Chuan Hwang,
Tsunglin Liu ,
Darby Tien-Hao Chang

**Abstract:**

De novo genome assembly is always fragmented. Assembly fragmentation is more serious using the popular next generation sequencing (NGS) data because NGS sequences are shorter than the traditional Sanger sequences. As the data throughput of NGS is high, the fragmentations in assemblies are usually not the result of missing data. On the contrary, the assembled sequences, called contigs, are often connected to more than one other contigs in a complicated manner, leading to the fragmentations. False connections in such complicated connections between contigs, named a contig graph, are inevitable because of repeats and sequencing/assembly errors. Simplifying a contig graph by removing false connections directly improves genome assembly. In this work, we have developed a tool, SIMGraph, to resolve ambiguous connections between contigs using NGS data. Applying SIMGraph to the assembly of a fungus and a fish genome, we resolved 27.6% and 60.3% ambiguous contig connections, respectively. These results can reduce the experimental efforts in resolving contig connections.

**Keywords:**
Contig graph,
NGS,
de novo assembly,
scaffold.

##### 8855 A Lifetime-Guaranteed Routing Scheme in Wireless Sensor Networks

**Authors:**
Jae Keun Park,
Sung Je Hong,
Kyong Hoon Kim,
Tae Heum Kang,
Wan Yeon Lee

**Abstract:**

**Keywords:**
Sensor network,
battery,
residual lifetime,
routingscheme,
QoS

##### 8854 Analyzing the Factors that Cause Parallel Performance Degradation in Parallel Graph-Based Computations Using Graph500

**Authors:**
Mustafa Elfituri,
Jonathan Cook

**Abstract:**

Recently, graph-based computations have become more important in large-scale scientific computing as they can provide a methodology to model many types of relations between independent objects. They are being actively used in fields as varied as biology, social networks, cybersecurity, and computer networks. At the same time, graph problems have some properties such as irregularity and poor locality that make their performance different than regular applications performance. Therefore, parallelizing graph algorithms is a hard and challenging task. Initial evidence is that standard computer architectures do not perform very well on graph algorithms. Little is known exactly what causes this. The Graph500 benchmark is a representative application for parallel graph-based computations, which have highly irregular data access and are driven more by traversing connected data than by computation. In this paper, we present results from analyzing the performance of various example implementations of Graph500, including a shared memory (OpenMP) version, a distributed (MPI) version, and a hybrid version. We measured and analyzed all the factors that affect its performance in order to identify possible changes that would improve its performance. Results are discussed in relation to what factors contribute to performance degradation.

**Keywords:**
Graph computation,
Graph500 benchmark,
parallel architectures,
parallel programming,
workload characterization.

##### 8853 Analysis of Electrical Networks Using Phasors: A Bond Graph Approach

**Authors:**
Israel Núñez-Hernández,
Peter C. Breedveld,
Paul B. T. Weustink,
Gilberto Gonzalez-A

**Abstract:**

This paper proposes a phasor representation of electrical networks by using bond graph methodology. A so-called phasor bond graph is built up by means of two-dimensional bonds, which represent the complex plane. Impedances or admittances are used instead of the standard bond graph elements. A procedure to obtain the steady-state values from a phasor bond graph model is presented. Besides the presentation of a phasor bond graph library in SIDOPS code, also an application example is discussed.

**Keywords:**
Bond graphs,
phasor theory,
steady-state,
complex
power,
electrical networks.