Search results for: 2-Connected planar graph

Authors: Jeffrey L. Duffany

Abstract:

Graph coloring is an important problem in computer science and many algorithms are known for obtaining reasonably good solutions in polynomial time. One method of comparing different algorithms is to test them on a set of standard graphs where the optimal solution is already known. This investigation analyzes a set of 50 well known graph coloring instances according to a set of complexity measures. These instances come from a variety of sources some representing actual applications of graph coloring (register allocation) and others (mycieleski and leighton graphs) that are theoretically designed to be difficult to solve. The size of the graphs ranged from ranged from a low of 11 variables to a high of 864 variables. The method used to solve the coloring problem was the square of the adjacency (i.e., correlation) matrix. The results show that the most difficult graphs to solve were the leighton and the queen graphs. Complexity measures such as density, mobility, deviation from uniform color class size and number of block diagonal zeros are calculated for each graph. The results showed that the most difficult problems have low mobility (in the range of .2-.5) and relatively little deviation from uniform color class size.

Keywords: graph coloring, complexity, algorithm.

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

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 548

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 2035

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 1701

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 2553

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 2263

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 1451

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 1874

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 1618

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 2118

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 716

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 1722

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 3495

Authors: Yue Zhao, Chao Li

Abstract:

Camera calibration is an important step in 3D reconstruction. Camera calibration may be classified into two major types: traditional calibration and self-calibration. However, a calibration method in using a checkerboard is intermediate between traditional calibration and self-calibration. A self is proposed based on a square in this paper. Only a square in the planar template, the camera self-calibration can be completed through the single view. The proposed algorithm is that the virtual circle and straight line are established by a square on planar template, and circular points, vanishing points in straight lines and the relation between them are be used, in order to obtain the image of the absolute conic (IAC) and establish the camera intrinsic parameters. To make the calibration template is simpler, as compared with the Zhang Zhengyou-s method. Through real experiments and experiments, the experimental results show that this algorithm is feasible and available, and has a certain precision and robustness.

Keywords: Absolute conic, camera calibration, circle point, vanishing point.

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

Authors: T. Benyetho, L. El Abdellaoui, J. Terhzaz, H. Bennis, N. Ababssi, A. Tajmouati, A. Tribak, M. Latrach

Abstract:

This work presents a new planar multiband antenna based on fractal geometry. This structure is optimized and validated into simulation by using CST-MW Studio. To feed this antenna we have used a CPW line which makes it easy to be incorporated with integrated circuits. The simulation results presents a good matching input impedance and radiation pattern in the GSM band at 900 MHz and ISM band at 2.4 GHz. The final structure is a dual band fractal antenna with 70 x 70 mm² as a total area by using an FR4 substrate.

Keywords: Antenna, CPW, Fractal, GSM, Multiband.

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

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 2642

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 1547

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 953

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 3036

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 806

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 1727

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 1204

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 1668

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 1693

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 2477

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.

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

Authors: Aicha Majda, Abdelhamid El Hassani

Abstract:

Lung CT image segmentation is a prerequisite in lung CT image analysis. Most of the conventional methods need a post-processing to deal with the abnormal lung CT scans such as lung nodules or other lesions. The simplest similarity measure in the standard Graph Cuts Algorithm consists of directly comparing the pixel values of the two neighboring regions, which is not accurate because this kind of metrics is extremely sensitive to minor transformations such as noise or other artifacts problems. In this work, we propose an improved version of the standard graph cuts algorithm based on the Patch-Based similarity metric. The boundary penalty term in the graph cut algorithm is defined Based on Patch-Based similarity measurement instead of the simple intensity measurement in the standard method. The weights between each pixel and its neighboring pixels are Based on the obtained new term. The graph is then created using theses weights between its nodes. Finally, the segmentation is completed with the minimum cut/Max-Flow algorithm. Experimental results show that the proposed method is very accurate and efficient, and can directly provide explicit lung regions without any post-processing operations compared to the standard method.

Keywords: Graph cuts, lung CT scan, lung parenchyma segmentation, patch based similarity metric.

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

Authors: M. Farshbaf, M. R. Feizi-Derakhshi

Abstract:

Graph partitioning is a NP-hard problem with multiple conflicting objectives. The graph partitioning should minimize the inter-partition relationship while maximizing the intra-partition relationship. Furthermore, the partition load should be evenly distributed over the respective partitions. Therefore this is a multiobjective optimization problem (MOO). One of the approaches to MOO is Pareto optimization which has been used in this paper. The proposed methods of this paper used to improve the performance are injecting best solutions of previous runs into the first generation of next runs and also storing the non-dominated set of previous generations to combine with later generation's non-dominated set. These improvements prevent the GA from getting stuck in the local optima and increase the probability of finding more optimal solutions. Finally, a simulation research is carried out to investigate the effectiveness of the proposed algorithm. The simulation results confirm the effectiveness of the proposed method.

Keywords: Graph partitioning, Genetic algorithm, Multiobjective optimization, Pareto front.

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

Authors: Wen-Fang Peng, Justie Su-Tzu Juan

Abstract:

The balanced Hamiltonian cycle problemis a quiet new topic of graph theorem. Given a graph G = (V, E), whose edge set can be partitioned into k dimensions, for positive integer k and a Hamiltonian cycle C on G. The set of all i-dimensional edge of C, which is a subset by E(C), is denoted as Ei(C).

Keywords: Hamiltonian cycle, balanced, Cartesian product.

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

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 1794