Search results for: Graph drawing.
Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 462

Search results for: Graph drawing.

462 A Force-directed Graph Drawing based on the Hierarchical Individual Timestep Method

Authors: T. Matsubayashi, T. Yamada

Abstract:

In this paper, we propose a fast and efficient method for drawing very large-scale graph data. The conventional force-directed method proposed by Fruchterman and Rheingold (FR method) is well-known. It defines repulsive forces between every pair of nodes and attractive forces between connected nodes on a edge and calculates corresponding potential energy. An optimal layout is obtained by iteratively updating node positions to minimize the potential energy. Here, the positions of the nodes are updated every global timestep at the same time. In the proposed method, each node has its own individual time and time step, and nodes are updated at different frequencies depending on the local situation. The proposed method is inspired by the hierarchical individual time step method used for the high accuracy calculations for dense particle fields such as star clusters in astrophysical dynamics. Experiments show that the proposed method outperforms the original FR method in both speed and accuracy. We implement the proposed method on the MDGRAPE-3 PCI-X special purpose parallel computer and realize a speed enhancement of several hundred times.

Keywords: visualization, graph drawing, Internet Map

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1857
461 Modeling of Kepler-Poinsot Solid Using Isomorphic Polyhedral Graph

Authors: Hidetoshi Nonaka

Abstract:

This paper presents an interactive modeling system of uniform polyhedra using the isomorphic graphs. Especially, Kepler-Poinsot solids are formed by modifications of dodecahedron and icosahedron.

Keywords: Kepler-Poinsot solid, Shape modeling, Polyhedralgraph, Graph drawing.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1796
460 Courses Pre-Required Visualization Using Force Directed Placement Technique

Authors: Imen Ammari, Mourad Elloumi, Ala Eddine Barouni

Abstract:

Visualizing “Courses – Pre – Required - Architecture" on the screen has proven to be useful and helpful for university actors and specially for students. In fact, these students can easily identify courses and their pre required, perceive the courses to follow in the future, and then can choose rapidly the appropriate course to register in. Given a set of courses and their prerequired, we present an algorithm for visualization a graph entitled “Courses-Pre-Required-Graph" that present courses and their prerequired in order to help students to recognize, lonely, what courses to take in the future and perceive the contain of all courses that they will study. Our algorithm using “Force Directed Placement" technique visualizes the “Courses-Pre-Required-Graph" in such way that courses are easily identifiable. The time complexity of our drawing algorithm is O (n2), where n is the number of courses in the “Courses-Pre-Required-Graph".

Keywords: Courses–Pre-Required-Architecture, Courses-Pre- Required-Graph, Courses-Pre-Required-Visualization, Force directed Placement, Resolution.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1322
459 Efficient Filtering of Graph Based Data Using Graph Partitioning

Authors: Nileshkumar Vaishnav, Aditya Tatu

Abstract:

An algebraic framework for processing graph signals axiomatically designates the graph adjacency matrix as the shift operator. In this setup, we often encounter a problem wherein we know the filtered output and the filter coefficients, and need to find out the input graph signal. Solution to this problem using direct approach requires O(N3) operations, where N is the number of vertices in graph. In this paper, we adapt the spectral graph partitioning method for partitioning of graphs and use it to reduce the computational cost of the filtering problem. We use the example of denoising of the temperature data to illustrate the efficacy of the approach.

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

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1239
458 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 1657
457 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.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1073
456 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.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1263
455 N-Sun Decomposition of Complete, Complete Bipartite and Some Harary Graphs

Authors: R. Anitha, R. S. Lekshmi

Abstract:

Graph decompositions are vital in the study of combinatorial design theory. A decomposition of a graph G is a partition of its edge set. An n-sun graph is a cycle Cn with an edge terminating in a vertex of degree one attached to each vertex. In this paper, we define n-sun decomposition of some even order graphs with a perfect matching. We have proved that the complete graph K2n, complete bipartite graph K2n, 2n and the Harary graph H4, 2n have n-sun decompositions. A labeling scheme is used to construct the n-suns.

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

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2400
454 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.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1645
453 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

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1187
452 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.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1205
451 Metric Dimension on Line Graph of Honeycomb Networks

Authors: M. Hussain, Aqsa Farooq

Abstract:

Let G = (V,E) be a connected graph and distance between any two vertices a and b in G is a−b geodesic and is denoted by d(a, b). A set of vertices W resolves a graph G if each vertex is uniquely determined by its vector of distances to the vertices in W. A metric dimension of G is the minimum cardinality of a resolving set of G. In this paper line graph of honeycomb network has been derived and then we calculated the metric dimension on line graph of honeycomb network.

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

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 768
450 Comparison of Full Graph Methods of Switched Circuits Solution

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

Abstract:

As there are also graph methods of circuit analysis in addition to algebraic methods, it is, in theory, clearly possible to carry out an analysis of a whole switched circuit in two-phase switching exclusively by the graph method as well. This article deals with two methods of full-graph solving of switched circuits: by transformation graphs and by two-graphs. It deals with the circuit switched capacitors and the switched current, too. All methods are presented in an equally detailed steps to be able to compare.

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

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1314
449 Speedup Breadth-First Search by Graph Ordering

Authors: Qiuyi Lyu, Bin Gong

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.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 635
448 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 1519
447 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.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2023
446 Topological Queries on Graph-structured XML Data: Models and Implementations

Authors: Hongzhi Wang, Jianzhong Li, Jizhou Luo

Abstract:

In many applications, data is in graph structure, which can be naturally represented as graph-structured XML. Existing queries defined on tree-structured and graph-structured XML data mainly focus on subgraph matching, which can not cover all the requirements of querying on graph. In this paper, a new kind of queries, topological query on graph-structured XML is presented. This kind of queries consider not only the structure of subgraph but also the topological relationship between subgraphs. With existing subgraph query processing algorithms, efficient algorithms for topological query processing are designed. Experimental results show the efficiency of implementation algorithms.

Keywords: XML, Graph Structure, Topological query.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1416
445 An Efficient Graph Query Algorithm Based on Important Vertices and Decision Features

Authors: Xiantong Li, Jianzhong Li

Abstract:

Graph has become increasingly important in modeling complicated structures and schemaless data such as proteins, chemical compounds, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database via graph-based indices. Different from the existing methods, our approach, called VFM (Vertex to Frequent Feature Mapping), makes use of vertices and decision features as the basic indexing feature. VFM constructs two mappings between vertices and frequent features to answer graph queries. The VFM approach not only provides an elegant solution to the graph indexing problem, but also demonstrates how database indexing and query processing can benefit from data mining, especially frequent pattern mining. The results show that the proposed method not only avoids the enumeration method of getting subgraphs of query graph, but also effectively reduces the subgraph isomorphism tests between the query graph and graphs in candidate answer set in verification stage.

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

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1874
444 Notes on Fractional k-Covered Graphs

Authors: Sizhong Zhou, Yang Xu

Abstract:

A graph G is fractional k-covered if for each edge e of G, there exists a fractional k-factor h, such that h(e) = 1. If k = 2, then a fractional k-covered graph is called a fractional 2-covered graph. The binding number bind(G) is defined as follows, bind(G) = min{|NG(X)| |X| : ├ÿ = X Ôèå V (G),NG(X) = V (G)}. In this paper, it is proved that G is fractional 2-covered if δ(G) ≥ 4 and bind(G) > 5 3 .

Keywords: graph, binding number, fractional k-factor, fractional k-covered graph.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1196
443 Syntactic Recognition of Distorted Patterns

Authors: Marek Skomorowski

Abstract:

In syntactic pattern recognition a pattern can be represented by a graph. Given an unknown pattern represented by a graph g, the problem of recognition is to determine if the graph g belongs to a language L(G) generated by a graph grammar G. The so-called IE graphs have been defined in [1] for a description of patterns. The IE graphs are generated by so-called ETPL(k) graph grammars defined in [1]. An efficient, parsing algorithm for ETPL(k) graph grammars for syntactic recognition of patterns represented by IE graphs has been presented in [1]. In practice, structural descriptions may contain pattern distortions, so that the assignment of a graph g, representing an unknown pattern, to a graph language L(G) generated by an ETPL(k) graph grammar G is rejected by the ETPL(k) type parsing. Therefore, there is a need for constructing effective parsing algorithms for recognition of distorted patterns. The purpose of this paper is to present a new approach to syntactic recognition of distorted patterns. To take into account all variations of a distorted pattern under study, a probabilistic description of the pattern is needed. A random IE graph approach is proposed here for such a description ([2]).

Keywords: Syntactic pattern recognition, Distorted patterns, Random graphs, Graph grammars.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1396
442 Applying Hybrid Graph Drawing and Clustering Methods on Stock Investment Analysis

Authors: Mouataz Zreika, Maria Estela Varua

Abstract:

Stock investment decisions are often made based on current events of the global economy and the analysis of historical data. Conversely, visual representation could assist investors’ gain deeper understanding and better insight on stock market trends more efficiently. The trend analysis is based on long-term data collection. The study adopts a hybrid method that combines the Clustering algorithm and Force-directed algorithm to overcome the scalability problem when visualizing large data. This method exemplifies the potential relationships between each stock, as well as determining the degree of strength and connectivity, which will provide investors another understanding of the stock relationship for reference. Information derived from visualization will also help them make an informed decision. The results of the experiments show that the proposed method is able to produced visualized data aesthetically by providing clearer views for connectivity and edge weights.

Keywords: Clustering, force-directed, graph drawing, stock investment analysis.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1595
441 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: Classification, Directional image, Fingerprint, Graph, Super graph.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3637
440 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 1868
439 Image Segmentation Using Suprathreshold Stochastic Resonance

Authors: Rajib Kumar Jha, P.K.Biswas, B.N.Chatterji

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.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1230
438 Analysis of a Singular Perturbed Synchronous Generator with a Bond Graph Approach

Authors: Gilberto Gonzalez-A, Noe Barrera-G

Abstract:

An analysis of a synchronous generator in a bond graph approach is proposed. This bond graph allows to determine the simplified models of the system by using singular perturbations. Firstly, the nonlinear bond graph of the generator is linearized. Then, the slow and fast state equations by applying singular perturbations are obtained. Also, a bond graph to get the quasi-steady state of the slow dynamic is proposed. In order to verify the effectiveness of the singularly perturbed models, simulation results of the complete system and reduced models are shown.

Keywords: Bond graph modelling, synchronous generator, singular perturbations

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1699
437 SEM-EBSD Observation for Microtubes by Using Dieless Drawing Process

Authors: Takashi Sakai, Itaru Kumisawa

Abstract:

Because die drawing requires insertion of a die, a plug, or a mandrel, higher precision and efficiency are demanded for drawing equipment for a tube having smaller diameter. Manufacturing of such tubes is also accompanied by problems such as cracking and fracture. We specifically examine dieless drawing, which is less affected by these drawing-related difficulties. This deformation process is governed by a similar principle to that of reduction in diameter when pulling a heated glass tube. We conducted dieless drawing of SUS304 stainless steel microtubes under various conditions with three factor parameters of heating temperature, area reduction, and drawing speed. We used SEM-EBSD to observe the processing condition effects on microstructural elements. As the result of this study, crystallographic orientation of microtube is clear by using SEM-EBSD analysis.

Keywords: Microtube, dieless drawing, IPF, inverse pole figure, GOS, grain orientation spread, crystallographic analysis.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 772
436 Connected Vertex Cover in 2-Connected Planar Graph with Maximum Degree 4 is NP-complete

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

Abstract:

This paper proves that the problem of finding connected vertex cover in a 2-connected planar graph ( CVC-2 ) with maximum degree 4 is NP-complete. The motivation for proving this result is to give a shorter and simpler proof of NP-Completeness of TRA-MLC (the Top Right Access point Minimum-Length Corridor) problem [1], by finding the reduction from CVC-2. TRA-MLC has many applications in laying optical fibre cables for data communication and electrical wiring in floor plans.The problem of finding connected vertex cover in any planar graph ( CVC ) with maximum degree 4 is NP-complete [2]. We first show that CVC-2 belongs to NP and then we find a polynomial reduction from CVC to CVC-2. Let a graph G0 and an integer K form an instance of CVC, where G0 is a planar graph and K is an upper bound on the size of the connected vertex cover in G0. We construct a 2-connected planar graph, say G, by identifying the blocks and cut vertices of G0, and then finding the planar representation of all the blocks of G0, leading to a plane graph G1. We replace the cut vertices with cycles in such a way that the resultant graph G is a 2-connected planar graph with maximum degree 4. We consider L = K -2t+3 t i=1 di where t is the number of cut vertices in G1 and di is the number of blocks for which ith cut vertex is common. We prove that G will have a connected vertex cover with size less than or equal to L if and only if G0 has a connected vertex cover of size less than or equal to K.

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

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2005
435 Protein Graph Partitioning by Mutually Maximization of cycle-distributions

Authors: Frank Emmert Streib

Abstract:

The classification of the protein structure is commonly not performed for the whole protein but for structural domains, i.e., compact functional units preserved during evolution. Hence, a first step to a protein structure classification is the separation of the protein into its domains. We approach the problem of protein domain identification by proposing a novel graph theoretical algorithm. We represent the protein structure as an undirected, unweighted and unlabeled graph which nodes correspond the secondary structure elements of the protein. This graph is call the protein graph. The domains are then identified as partitions of the graph corresponding to vertices sets obtained by the maximization of an objective function, which mutually maximizes the cycle distributions found in the partitions of the graph. Our algorithm does not utilize any other kind of information besides the cycle-distribution to find the partitions. If a partition is found, the algorithm is iteratively applied to each of the resulting subgraphs. As stop criterion, we calculate numerically a significance level which indicates the stability of the predicted partition against a random rewiring of the protein graph. Hence, our algorithm terminates automatically its iterative application. We present results for one and two domain proteins and compare our results with the manually assigned domains by the SCOP database and differences are discussed.

Keywords: Graph partitioning, unweighted graph, protein domains.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1358
434 Eccentric Connectivity Index, First and Second Zagreb Indices of Corona Graph

Authors: A. Kulandai Therese

Abstract:

The eccentric connectivity index based on degree and eccentricity of the vertices of a graph is a widely used graph invariant in mathematics. In this paper, we present the explicit eccentric connectivity index, first and second Zagreb indices for a Corona graph and sub divisionrelated corona graphs.

Keywords: Corona graph, Degree, Eccentricity, Eccentric Connectivity Index, First Zagreb index, Second Zagreb index and Subdivision graphs.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2662
433 Analysis of a Hydroelectric Plant connected to Electrical Power System in the Physical Domain

Authors: Gilberto Gonzalez-A, Octavio Barriga

Abstract:

A bond graph model of a hydroelectric plant is proposed. In order to analyze the system some structural properties of a bond graph are used. The structural controllability of the hydroelctric plant is described. Also, the steady state of the state variables applying the bond graph in a derivative causality assignment is obtained. Finally, simulation results of the system are shown.

Keywords: Bond graph, hydraulic plant, steady state.

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