Search results for: Graph drawing.
400 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.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 532399 The Experimental and Numerical Analysis of Trip Steel Wire Drawing Processes Drawn with Different Partial Reductions
Authors: Sylwia Wiewiorowska, Zbigniew Muskalski
Abstract:
The strain intensity and redundant strains, dependent in multistage TRIP wire drawing processes from values used single partial reductions, should influence on the intensity of transformation the retained austenite into martensite and thereby on mechanical properties of drawn wires. The numerical analysis of drawing processes with use of Drawing 2D programme, for steel wires made from TRIP steel with 0,29% has been shown in the work. The change of strain intensity εc and the values of redundant strain εxy, has been determined for particular draws in dependence of used single partial reductions.Keywords: Steel wire, TRIP steel, drawing processes, fem modelling.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1527398 The Influence of Surface Roughness of Drawbead on Non-Symmetry Deep Drawing Cold Rolled Steel Sheet
Authors: A. Watanapa, S. Torsakul
Abstract:
This study was aimed to explain the influence of surface roughness of the drawbead on non-symmetry deep drawing cold rolled steel sheet to improve the drawability of cold rolled steel sheet. The variables used in this study included semi-circle drawbead with 3 levels of surface roughness which are 6.127 mm Ra, 0.963 mm Ra and 0.152 mm Ra and cold rolled steel sheet according to 3 grades of the JIS standards which are SPCC, SPCE and SPCD with the thickness of 1.0 mm and the blankholder force which is 50% of the drawing force and the depth of 50 mm. According to the test results, when there was the increase in the surface roughness of drawbead, there would be the increase in deep drawing force, especially the SPCC cold rolled steel sheet. This is similar to the increase in the equivalent strain and the wall thickness distribution when the surface roughness of the drawbead increased. It could be concluded that the surface roughness of drawbead has an influence on deep drawing cold rolled steel sheet, especially the drawing force, the equivalent strain and the wall thickness distribution.
Keywords: Drawbead, Deep Drawing, Drawing Force, Equivalent Strain, Surface roughness
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2412397 Prediction the Limiting Drawing Ratio in Deep Drawing Process by Back Propagation Artificial Neural Network
Authors: H.Mohammadi Majd, M.Jalali Azizpour, M. Goodarzi
Abstract:
In this paper back-propagation artificial neural network (BPANN) with Levenberg–Marquardt algorithm is employed to predict the limiting drawing ratio (LDR) of the deep drawing process. To prepare a training set for BPANN, some finite element simulations were carried out. die and punch radius, die arc radius, friction coefficient, thickness, yield strength of sheet and strain hardening exponent were used as the input data and the LDR as the specified output used in the training of neural network. As a result of the specified parameters, the program will be able to estimate the LDR for any new given condition. Comparing FEM and BPANN results, an acceptable correlation was found.Keywords: BPANN, deep drawing, prediction, limiting drawingratio (LDR), Levenberg–Marquardt algorithm
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1848396 Approximating Maximum Weighted Independent Set Using Vertex Support
Authors: S. Balaji, V. Swaminathan, K. Kannan
Abstract:
The Maximum Weighted Independent Set (MWIS) problem is a classic graph optimization NP-hard problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the MWIS problem is to find a vertex set S V whose total weight is maximum subject to no two vertices in S are adjacent. This paper presents a novel approach to approximate the MWIS of a graph using minimum weighted vertex cover of the graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the proposed algorithm can yield better solutions than other existing algorithms found in the literature for solving the MWIS.Keywords: weighted independent set, vertex cover, vertex support, heuristic, NP - hard problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2023395 Face Recognition using a Kernelization of Graph Embedding
Authors: Pang Ying Han, Hiew Fu San, Ooi Shih Yin
Abstract:
Linearization of graph embedding has been emerged as an effective dimensionality reduction technique in pattern recognition. However, it may not be optimal for nonlinearly distributed real world data, such as face, due to its linear nature. So, a kernelization of graph embedding is proposed as a dimensionality reduction technique in face recognition. In order to further boost the recognition capability of the proposed technique, the Fisher-s criterion is opted in the objective function for better data discrimination. The proposed technique is able to characterize the underlying intra-class structure as well as the inter-class separability. Experimental results on FRGC database validate the effectiveness of the proposed technique as a feature descriptor.Keywords: Face recognition, Fisher discriminant, graph embedding, kernelization.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1694394 Phasor Analysis of a Synchronous Generator: A Bond Graph Approach
Authors: Israel Núñez-Hernández, Peter C. Breedveld, Paul B. T. Weustink, Gilberto Gonzalez-A
Abstract:
This paper presents the use of phasor bond graphs to obtain the steady-state behavior of a synchronous generator. The phasor bond graph elements are built using 2D multibonds, which represent the real and imaginary part of the phasor. The dynamic bond graph model of a salient-pole synchronous generator is showed, and verified viz. a sudden short-circuit test. The reduction of the dynamic model into a phasor representation is described. The previous test is executed on the phasor bond graph model, and its steady-state values are compared with the dynamic response. Besides, the widely used power (torque)-angle curves are obtained by means of the phasor bond graph model, to test the usefulness of this model.
Keywords: Bond graphs, complex power, phasors, synchronous generator, short-circuit, open-circuit, power-angle curve.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2544393 N-Sun Decomposition of Complete Graphs and Complete Bipartite Graphs
Authors: R. Anitha, R. S. Lekshmi
Abstract:
Graph decompositions are vital in the study of combinatorial design theory. Given two graphs G and H, an H-decomposition of G is a partition of the edge set of G into disjoint isomorphic copies of H. An n-sun is a cycle Cn with an edge terminating in a vertex of degree one attached to each vertex. In this paper we have proved that the complete graph of order 2n, K2n can be decomposed into n-2 n-suns, a Hamilton cycle and a perfect matching, when n is even and for odd case, the decomposition is n-1 n-suns and a perfect matching. For an odd order complete graph K2n+1, delete the star subgraph K1, 2n and the resultant graph K2n is decomposed as in the case of even order. The method of building n-suns uses Walecki's construction for the Hamilton decomposition of complete graphs. A spanning tree decomposition of even order complete graphs is also discussed using the labeling scheme of n-sun decomposition. A complete bipartite graph Kn, n can be decomposed into n/2 n-suns when n/2 is even. When n/2 is odd, Kn, n can be decomposed into (n-2)/2 n-suns and a Hamilton cycle.Keywords: Hamilton cycle, n-sun decomposition, perfectmatching, spanning tree.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2253392 On the Use of Correlated Binary Model in Social Network Analysis
Authors: Elsayed A. Habib Elamir
Abstract:
In social network analysis the mean nodal degree and density of the graph can be considered as a measure of the activity of all actors in the network and this is an important property of a graph and for making comparisons among networks. Since subjects in a family or organization are subject to common environment factors, it is prime interest to study the association between responses. Therefore, we study the distribution of the mean nodal degree and density of the graph under correlated binary units. The cross product ratio is used to capture the intra-units association among subjects. Computer program and an application are given to show the benefits of the method.Keywords: Correlated Binary data, cross product ratio, densityof the graph, multiplicative binomial distribution.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1443391 A Further Study on the 4-Ordered Property of Some Chordal Ring Networks
Authors: Shin-Shin Kao, Hsiu-Chunj Pan
Abstract:
Given a graph G. A cycle of G is a sequence of vertices of G such that the first and the last vertices are the same. A hamiltonian cycle of G is a cycle containing all vertices of G. The graph G is k-ordered (resp. k-ordered hamiltonian) if for any sequence of k distinct vertices of G, there exists a cycle (resp. hamiltonian cycle) in G containing these k vertices in the specified order. Obviously, any cycle in a graph is 1-ordered, 2-ordered and 3- ordered. Thus the study of any graph being k-ordered (resp. k-ordered hamiltonian) always starts with k = 4. Most studies about this topic work on graphs with no real applications. To our knowledge, the chordal ring families were the first one utilized as the underlying topology in interconnection networks and shown to be 4-ordered. Furthermore, based on our computer experimental results, it was conjectured that some of them are 4-ordered hamiltonian. In this paper, we intend to give some possible directions in proving the conjecture.
Keywords: Hamiltonian cycle, 4-ordered, Chordal rings, 3-regular.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1862390 A NonLinear Observer of an Electrical Transformer: A Bond Graph Approach
Authors: Gilberto Gonzalez-A , Israel Nuñez
Abstract:
A bond graph model of an electrical transformer including the nonlinear saturation is presented. A nonlinear observer for the transformer based on multivariable circle criterion in the physical domain is proposed. In order to show the saturation and hysteresis effects on the electrical transformer, simulation results are obtained. Finally, the paper describes that convergence of the estimates to the true states is achieved.Keywords: Bond graph, nonlinear observer, electrical transformer, nonlinear saturation.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1605389 Identification of Optimum Parameters of Deep Drawing of a Cylindrical Workpiece using Neural Network and Genetic Algorithm
Authors: D. Singh, R. Yousefi, M. Boroushaki
Abstract:
Intelligent deep-drawing is an instrumental research field in sheet metal forming. A set of 28 different experimental data have been employed in this paper, investigating the roles of die radius, punch radius, friction coefficients and drawing ratios for axisymmetric workpieces deep drawing. This paper focuses an evolutionary neural network, specifically, error back propagation in collaboration with genetic algorithm. The neural network encompasses a number of different functional nodes defined through the established principles. The input parameters, i.e., punch radii, die radii, friction coefficients and drawing ratios are set to the network; thereafter, the material outputs at two critical points are accurately calculated. The output of the network is used to establish the best parameters leading to the most uniform thickness in the product via the genetic algorithm. This research achieved satisfactory results based on demonstration of neural networks.
Keywords: Deep-drawing, Neural network, Genetic algorithm, Sheet metal forming.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2189388 Binary Decision Diagrams: An Improved Variable Ordering using Graph Representation of Boolean Functions
Authors: P.W. C. Prasad, A. Assi, A. Harb, V.C. Prasad
Abstract:
This paper presents an improved variable ordering method to obtain the minimum number of nodes in Reduced Ordered Binary Decision Diagrams (ROBDD). The proposed method uses the graph topology to find the best variable ordering. Therefore the input Boolean function is converted to a unidirectional graph. Three levels of graph parameters are used to increase the probability of having a good variable ordering. The initial level uses the total number of nodes (NN) in all the paths, the total number of paths (NP) and the maximum number of nodes among all paths (MNNAP). The second and third levels use two extra parameters: The shortest path among two variables (SP) and the sum of shortest path from one variable to all the other variables (SSP). A permutation of the graph parameters is performed at each level for each variable order and the number of nodes is recorded. Experimental results are promising; the proposed method is found to be more effective in finding the variable ordering for the majority of benchmark circuits.
Keywords: Binary decision diagrams, graph representation, Boolean functions representation, variable ordering.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2098387 Total Chromatic Number of Δ-Claw-Free 3-Degenerated Graphs
Authors: Wongsakorn Charoenpanitseri
Abstract:
The total chromatic number χ"(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no incident or adjacent pair of elements receive the same color Let G be a graph with maximum degree Δ(G). Considering a total coloring of G and focusing on a vertex with maximum degree. A vertex with maximum degree needs a color and all Δ(G) edges incident to this vertex need more Δ(G) + 1 distinct colors. To color all vertices and all edges of G, it requires at least Δ(G) + 1 colors. That is, χ"(G) is at least Δ(G) + 1. However, no one can find a graph G with the total chromatic number which is greater than Δ(G) + 2. The Total Coloring Conjecture states that for every graph G, χ"(G) is at most Δ(G) + 2. In this paper, we prove that the Total Coloring Conjectur for a Δ-claw-free 3-degenerated graph. That is, we prove that the total chromatic number of every Δ-claw-free 3-degenerated graph is at most Δ(G) + 2.Keywords: Total colorings, the total chromatic number, 3-degenerated.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 698386 Finite Element Simulation of Deep Drawing Process to Minimize Earing
Authors: Pawan S. Nagda, Purnank S. Bhatt, Mit K. Shah
Abstract:
Earing defect in drawing process is highly undesirable not only because it adds on an additional trimming operation but also because the uneven material flow demands extra care. The objective of this work is to study the earing problem in the Deep Drawing of circular cup and to optimize the blank shape to reduce the earing. A finite element model is developed for 3-D numerical simulation of cup forming process in ABAQUS. Extra-deep-drawing (EDD) steel sheet has been used for simulation. Properties and tool design parameters were used as input for simulation. Earing was observed in the simulated cup and it was measured at various angles with respect to rolling direction. To reduce the earing defect initial blank shape was modified with the help of anisotropy coefficient. Modified blanks showed notable reduction in earing.Keywords: Finite element simulation, deep drawing, earing, anisotropy.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1978385 Steady State of Passive and Active Suspensions in the Physical Domain
Authors: Gilberto Gonzalez-A, Jorge Madrigal
Abstract:
The steady state response of bond graphs representing passive and active suspension is presented. A bond graph with preferred derivative causality assignment to get the steady state is proposed. A general junction structure of this bond graph is proposed. The proposed methodology to passive and active suspensions is applied.Keywords: Bond graph, steady state, active suspension.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1715384 Reductions of Control Flow Graphs
Authors: Robert Gold
Abstract:
Control flow graphs are a well-known representation of the sequential control flow 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 flow graphs. In this case the size of the graphs can grow considerably and thus makes it difficult for software engineers to analyze the control flow. Graph reductions are helpful in this situation. In this paper we define reductions to subsets of nodes. Since executions of programs are represented by paths through the control flow graphs, paths should be preserved. Furthermore, the composition of reductions makes a stepwise analysis approach possible.
Keywords: Control flow graph, graph reduction.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3485383 A Detailed Experimental Study and Evaluation of Springback under Stretch Bending Process
Authors: A. Soualem
Abstract:
The design of multi stage deep drawing processes requires the evaluation of many process parameters such as the intermediate die geometry, the blank shape, the sheet thickness, the blank holder force, friction, lubrication etc..These process parameters have to be determined for the optimum forming conditions before the process design. In general sheet metal forming may involve stretching drawing or various combinations of these basic modes of deformation. It is important to determine the influence of the process variables in the design of sheet metal working process. Especially, the punch and die corner for deep drawing will affect the formability. At the same time the prediction of sheet metals springback after deep drawing is an important issue to solve for the control of manufacturing processes. Nowadays, the importance of this problem increases because of the use of steel sheeting with high stress and also aluminum alloys.
The aim of this paper is to give a better understanding of the springback and its effect in various sheet metals forming process such as expansion and restreint deep drawing in the cup drawing process, by varying radius die, lubricant for two commercially available materials e.g. galvanized steel and Aluminum sheet. To achieve these goals experiments were carried out and compared with other results. The original of our purpose consist on tests which are ensured by adapting a U-type stretching-bending device on a tensile testing machine, where we studied and quantified the variation of the springback.
Keywords: Deep drawing, Expansion, Restreint deep drawing, Springback.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2518382 Angular-Coordinate Driven Radial Tree Drawing
Authors: Farshad Ghassemi Toosi, Nikola S. Nikolov
Abstract:
We present a visualization technique for radial drawing of trees consisting of two slightly different algorithms. Both of them make use of node-link diagrams for visual encoding. This visualization creates clear drawings without edge crossing. One of the algorithms is suitable for real-time visualization of large trees, as it requires minimal recalculation of the layout if leaves are inserted or removed from the tree; while the other algorithm makes better utilization of the drawing space. The algorithms are very similar and follow almost the same procedure but with different parameters. Both algorithms assign angular coordinates for all nodes which are then converted into 2D Cartesian coordinates for visualization. We present both algorithms and discuss how they compare to each other.
Keywords: Radial Tree Drawing, Real-Time Visualization, Angular Coordinates, Large Trees.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2592381 Modeling And Analysis of Simple Open Cycle Gas Turbine Using Graph Networks
Authors: Naresh Yadav, I.A. Khan, Sandeep Grover
Abstract:
This paper presents a unified approach based graph theory and system theory postulates for the modeling and analysis of Simple open cycle Gas turbine system. In the present paper, the simple open cycle gas turbine system has been modeled up to its subsystem level and system variables have been identified to develop the process subgraphs. The theorems and algorithms of the graph theory have been used to represent behavioural properties of the system like rate of heat and work transfers rates, pressure drops and temperature drops in the involved processes of the system. The processes have been represented as edges of the process subgraphs and their limits as the vertices of the process subgraphs. The system across variables and through variables has been used to develop terminal equations of the process subgraphs of the system. The set of equations developed for vertices and edges of network graph are used to solve the system for its process variables.Keywords: Simple open cycle gas turbine, Graph theoretic approach, process subgraphs, gas turbines system modeling, systemtheory
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2621380 Computing Maximum Uniquely Restricted Matchings in Restricted Interval Graphs
Authors: Swapnil Gupta, C. Pandu Rangan
Abstract:
A uniquely restricted matching is defined to be a matching M whose matched vertices induces a sub-graph which has only one perfect matching. In this paper, we make progress on the open question of the status of this problem on interval graphs (graphs obtained as the intersection graph of intervals on a line). We give an algorithm to compute maximum cardinality uniquely restricted matchings on certain sub-classes of interval graphs. We consider two sub-classes of interval graphs, the former contained in the latter, and give O(|E|^2) time algorithms for both of them. It is to be noted that both sub-classes are incomparable to proper interval graphs (graphs obtained as the intersection graph of intervals in which no interval completely contains another interval), on which the problem can be solved in polynomial time.Keywords: Uniquely restricted matching, interval graph, design and analysis of algorithms, matching, induced matching, witness counting.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1535379 Zero Divisor Graph of a Poset with Respect to Primal Ideals
Authors: Hossein Pourali
Abstract:
In this paper, we extend the concepts of primal and weakly primal ideals for posets. Further, the diameter of the zero divisor graph of a poset with respect to a non-primal ideal is determined. The relation between primary and primal ideals in posets is also studied.Keywords: Zero divisors graph, ideal, prime ideal, semiprime ideal, primal ideal, weakly primal ideal, associated prime ideal, primary ideal.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 944378 Bond Graph Modeling of Inter-Actuator Interactions in a Multi-Cylinder Hydraulic System
Authors: Mutuku Muvengei, John Kihiu
Abstract:
In this paper, a bond graph dynamic model for a valvecontrolled hydraulic cylinder has been developed. A simplified bond graph model of the inter-actuator interactions in a multi-cylinder hydraulic system has also been presented. The overall bond graph model of a valve-controlled hydraulic cylinder was developed by combining the bond graph sub-models of the pump, spool valve and the actuator using junction structures. Causality was then assigned in order to obtain a computational model which could be simulated. The causal bond graph model of the hydraulic cylinder was verified by comparing the open loop state responses to those of an ODE model which had been developed in literature based on the same assumptions. The results were found to correlate very well both in the shape of the curves, magnitude and the response times, thus indicating that the developed model represents the hydraulic dynamics of a valve-controlled cylinder. A simplified model for interactuator interaction was presented by connecting an effort source with constant pump pressure to the zero-junction from which the cylinders in a multi-cylinder system are supplied with a constant pressure from the pump. On simulating the state responses of the developed model under different situations of cylinder operations, indicated that such a simple model can be used to predict the inter-actuator interactions.Keywords: Bond graphs, Inter-actuator interactions, Valvecontrolledhydraulic cylinder.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3026377 Matching on Bipartite Graphs with Applications to School Course Registration Systems
Authors: Zhihan Li
Abstract:
Nowadays, most universities use the course enrollment system considering students’ registration orders. However, the students’ preference level to certain courses is also one important factor to consider. In this research, the possibility of applying a preference-first system has been discussed and analyzed compared to the order-first system. A bipartite graph is applied to resemble the relationship between students and courses they tend to register. With the graph set up, we apply Ford-Fulkerson (F.F.) Algorithm to maximize parings between two sets of nodes, in our case, students and courses. Two models are proposed in this paper: the one considered students’ order first, and the one considered students’ preference first. By comparing and contrasting the two models, we highlight the usability of models which potentially leads to better designs for school course registration systems.
Keywords: Bipartite graph, Ford-Fulkerson Algorithm, graph theory, maximum matching.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 783376 The Bipartite Ramsey Numbers b(C2m; C2n)
Authors: Rui Zhang, Yongqi Sun, and Yali Wu
Abstract:
Given bipartite graphs H1 and H2, the bipartite Ramsey number b(H1;H2) is the smallest integer b such that any subgraph G of the complete bipartite graph Kb,b, either G contains a copy of H1 or its complement relative to Kb,b contains a copy of H2. It is known that b(K2,2;K2,2) = 5, b(K2,3;K2,3) = 9, b(K2,4;K2,4) = 14 and b(K3,3;K3,3) = 17. In this paper we study the case that both H1 and H2 are even cycles, prove that b(C2m;C2n) ≥ m + n - 1 for m = n, and b(C2m;C6) = m + 2 for m ≥ 4.
Keywords: bipartite graph, Ramsey number, even cycle
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1710375 A Low Cost Knowledge Base System Framework for Design of Deep Drawing Die
Authors: Vishal Naranje, S. Kumar
Abstract:
In this paper a low cost knowledge base system (KBS) framework is proposed for design of deep drawing die and procedure for developing system modules. The task of building the system is structured into different modules for major activities of design of deep drawing die. A manufacturability assessment module of the proposed framework is developed to check the manufacturability of deep drawn parts. The technological knowledge is represented by using IF- THEN rules and it is coded in AutoLISP language. The module is designed to be loaded into the prompt area of AutoCAD. The cost of implementation of proposed system makes it affordable for small and medium scale sheet metal industries.Keywords: Knowledge base system, Deep drawing die, Manufacturability, Sheet metal.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2106374 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.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1186373 A New Self-stabilizing Algorithm for Maximal 2-packing
Authors: Zhengnan Shi
Abstract:
In the self-stabilizing algorithmic paradigm, each node has a local view of the system, in a finite amount of time the system converges to a global state with desired property. In a graph G = (V, E), a subset S C V is a 2-packing if Vi c V: IN[i] n SI <1. In this paper, an ID-based, constant space, self-stabilizing algorithm that stabilizes to a maximal 2-packing in an arbitrary graph is proposed. It is shown that the algorithm stabilizes in 0(n3) moves under any scheduler (daemon). Specifically, it is shown that the algorithm stabilizes in linear time-steps under a synchronous daemon where every privileged node moves at each time-step.Keywords: self-stabilization, 2-packing, distributed computing, fault tolerance, graph algorithms
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1660372 The Implementation of Spatio-Temporal Graph to Represent Situations in the Virtual World
Authors: Gung-Hun Jung, Jong-Hee Park
Abstract:
In this paper, we develop a Spatio-Temporal graph as of a key component of our knowledge representation Scheme. We design an integrated representation Scheme to depict not only present and past but future in parallel with the spaces in an effective and intuitive manner. The resulting multi-dimensional comprehensive knowledge structure accommodates multi-layered virtual world developing in the time to maximize the diversity of situations in the historical context. This knowledge representation Scheme is to be used as the basis for simulation of situations composing the virtual world and for implementation of virtual agents' knowledge used to judge and evaluate the situations in the virtual world. To provide natural contexts for situated learning or simulation games, the virtual stage set by this Spatio-Temporal graph is to be populated by agents and other objects interrelated and changing which are abstracted in the ontology.Keywords: Ontology, Virtual Reality, Spatio-Temporal graph.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1682371 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.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2454