Dissertations / Theses on the topic 'Graph problems'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Graph problems.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Pantel, Sarah. "Graph packing problems." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape9/PQDD_0028/MQ51442.pdf.
Full textBessy, Stéphane. "Some problems in graph theory and graphs algorithmic theory." Habilitation à diriger des recherches, Université Montpellier II - Sciences et Techniques du Languedoc, 2012. http://tel.archives-ouvertes.fr/tel-00806716.
Full textNikwigize, Adolphe. "Graph theory : Route problems." Thesis, Linnéuniversitetet, Institutionen för datavetenskap, fysik och matematik, DFM, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-17397.
Full textRackham, Tom. "Problems in graph colouring." Thesis, University of Oxford, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.526104.
Full textVarga, Romy Carleton University Dissertation Mathematics. "Graph connectivity augmentation problems." Ottawa, 1996.
Find full textBush, Albert. "Two Problems on Bipartite Graphs." Digital Archive @ GSU, 2009. http://digitalarchive.gsu.edu/math_theses/72.
Full textCasselgren, Carl Johan. "On some graph coloring problems." Doctoral thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-43389.
Full textHe, Dayu. "Algorithms for Graph Drawing Problems." Thesis, State University of New York at Buffalo, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10284151.
Full textA graph G is called planar if it can be drawn on the plan such that no two distinct edges intersect each other but at common endpoints. Such drawing is called a plane embedding of G. A plane graph is a graph with a fixed embedding. A straight-line drawing G of a graph G = (V, E) is a drawing where each vertex of V is drawn as a distinct point on the plane and each edge of G is drawn as a line segment connecting two end vertices. In this thesis, we study a set of planar graph drawing problems.
First, we consider the problem of monotone drawing: A path P in a straight line drawing Γ is monotone if there exists a line l such that the orthogonal projections of the vertices of P on l appear along l in the order they appear in P. We call l a monotone line (or monotone direction) of P. G is called a monotone drawing of G if it contains at least one monotone path Puw between every pair of vertices u,w of G. Monotone drawings were recently introduced by Angelini et al. and represent a new visualization paradigm, and is also closely related to several other important graph drawing problems. As in many graph drawing problems, one of the main concerns of this research is to reduce the drawing size, which is the size of the smallest integer grid such that every graph in the graph class can be drawn in such a grid. We present two approaches for the problem of monotone drawings of trees. Our first approach show that every n-vertex tree T admits a monotone drawing on a grid of size O(n1.205) × O( n1.205) grid. Our second approach further reduces the size of drawing to 12n × 12n, which is asymptotically optimal. Both of our two drawings can be constructed in O(n) time.
We also consider monotone drawings of 3-connected plane graphs. We prove that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a f × f grid, which can be constructed in O(n) time.
Second, we consider the problem of orthogonal drawing. An orthogonal drawing of a plane graph G is a planar drawing of G such that each vertex of G is drawn as a point on the plane, and each edge is drawn as a sequence of horizontal and vertical line segments with no crossings. Orthogonal drawing has attracted much attention due to its various applications in circuit schematics, relationship diagrams, data flow diagrams etc. . Rahman et al. gave a necessary and sufficient condition for a plane graph G of maximum degree 3 to have an orthogonal drawing without bends. An orthogonal drawing D(G) is orthogonally convex if all faces of D(G) are orthogonally convex polygons. Chang et al. gave a necessary and sufficient condition (which strengthens the conditions in the previous result) for a plane graph G of maximum degree 3 to have an orthogonal convex drawing without bends. We further strengthen the results such that if G satisfies the same conditions as in previous papers, it not only has an orthogonally convex drawing, but also a stronger star-shaped orthogonal drawing.
Lahn, Nathaniel Adam. "A Separator-Based Framework for Graph Matching Problems." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/98618.
Full textDoctor of Philosophy
Assume we are given a list of objects, and a list of compatible pairs of these objects. A matching consists of a chosen subset of these compatible pairs, where each object participates in at most one chosen pair. For any chosen pair of objects, we say the these two objects are matched. Generally, we seek to maximize the number of compatible matches. A maximum cardinality matching is a matching with the largest possible size. In many cases, there are multiple options for maximizing the number of compatible pairings. While maximizing the size of the matching is often the primary concern, one may also seek to minimize the cost of the matching. This is known as the minimum-cost maximum-cardinality matching problem. These two matching problems have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Our interest is in the design of algorithms for both of these problems that are efficiently scalable, even as the number of objects involved grows very large. To aid in the design of scalable algorithms, we observe that some inputs have good separators, meaning that by removing some subset S of objects, one can divide the remaining objects into two sets V and V', where all pairs of objects between V and V' are incompatible. We design several new algorithms that exploit good separators, and prove that these algorithms scale better than previously existing approaches.
Edwards, C. S. "Some extremal problems in graph theory." Thesis, University of Reading, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.373467.
Full textGrinshpun, Andrey Vadim. "Some problems in Graph Ramsey Theory." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/97767.
Full textThis electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 149-156).
A graph G is r-Ramsey minimal with respect to a graph H if every r-coloring of the edges of G yields a monochromatic copy of H, but the same is not true for any proper subgraph of G. The study of the properties of graphs that are Ramsey minimal with respect to some H and similar problems is known as graph Ramsey theory; we study several problems in this area. Burr, Erdös, and Lovász introduced s(H), the minimum over all G that are 2- Ramsey minimal for H of [delta](G), the minimum degree of G. We find the values of s(H) for several classes of graphs H, most notably for all 3-connected bipartite graphs which proves many cases of a conjecture due to Szabó, Zumstein, and Zürcher. One natural question when studying graph Ramsey theory is what happens when, rather than considering all 2-colorings of a graph G, we restrict to a subset of the possible 2-colorings. Erdös and Hajnal conjectured that, for any fixed color pattern C, there is some [epsilon] > 0 so that every 2-coloring of the edges of a Kn, the complete graph on n vertices, which doesn't contain a copy of C contains a monochromatic clique on n[epsilon] vertices. Hajnal generalized this conjecture to more than 2 colors and asked in particular about the case when the number of colors is 3 and C is a rainbow triangle (a K3 where each edge is a different color); we prove Hajnal's conjecture for rainbow triangles. One may also wonder what would happen if we wish to cover all of the vertices with monochromatic copies of graphs. Let F = {F₁, F₂, . . .} be a sequence of graphs such that Fn is a graph on n vertices with maximum degree at most [delta]. If each Fn is bipartite, then the vertices of any 2-edge-colored complete graph can be partitioned into at most 2C[delta] vertex disjoint monochromatic copies of graphs from F, where C is an absolute constant. This result is best possible, up to the constant C.
by Andrey Vadim Grinshpun.
Ph. D.
Husbands, Parry. "Solving graph connectivity problems on JAGs." Thesis, Massachusetts Institute of Technology, 1994. http://hdl.handle.net/1721.1/36509.
Full textYodpinyanee, Anak. "Sub-linear algorithms for graph problems." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120411.
Full textCataloged from PDF version of thesis.
Includes bibliographical references (pages 189-199).
In the face of massive data sets, classical algorithmic models, where the algorithm reads the entire input, performs a full computation, then reports the entire output, are rendered infeasible. To handle these data sets, alternative algorithmic models are suggested to solve problems under the restricted, namely sub-linear, resources such as time, memory or randomness. This thesis aims at addressing these limitations on graph problems and combinatorial optimization problems through a number of different models. First, we consider the graph spanner problem in the local computation algorithm (LCA) model. A graph spanner is a subgraph of the input graph that preserves all pairwise distances up to a small multiplicative stretch. Given a query edge from the input graph, the LCA explores a sub-linear portion of the input graph, then decides whether to include this edge in its spanner or not - the answers to all edge queries constitute the output of the LCA. We provide the first LCA constructions for 3 and 5-spanners of general graphs with almost optimal trade-offs between spanner sizes and stretches, and for fixed-stretch spanners of low maximum-degree graphs. Next, we study the set cover problem in the oracle access model. The algorithm accesses a sub-linear portion of the input set system by probing for elements in a set, and for sets containing an element, then computes an approximate minimum set cover: a collection of an approximately-minimum number of sets whose union includes all elements. We provide probe-efficient algorithms for set cover, and complement our results with almost tight lower bound constructions. We further extend our study to the LP-relaxation variants and to the streaming setting, obtaining the first streaming results for the fractional set cover problem. Lastly, we design local-access generators for a collection of fundamental random graph models. We demonstrate how to generate graphs according to the desired probability distribution in an on-the-fly fashion. Our algorithms receive probes about arbitrary parts of the input graph, then construct just enough of the graph to answer these probes, using only polylogarithmic time, additional space and random bits per probe. We also provide the first implementation of random neighbor probes, which is a basic algorithmic building block with applications in various huge graph models.
by Anak Yodpinyanee.
Ph. D.
Weaver, Robert Wooddell. "Some problems in structural graph theory /." The Ohio State University, 1986. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487268021746449.
Full textRen, Jintong. "Optimization algorithms for graph layout problems." Thesis, Angers, 2020. https://tel.archives-ouvertes.fr/tel-03178385.
Full textThis thesis considers two graph layout problems: the cyclic bandwidth problem (CBP) and the minimum linear arrangement problem (MinLA). The CBP is a natural extension of the bandwidth minimization problem (BMP) and the MinLA is a min-sum problem. These problems are widely applied in the real life. Since they are NP-hard problems, it is computational difficult to solve them in the general case. Therefore, this thesis is dedicated to developing effective heuristic algorithms to deal with these challenging problems.Specifically, we introduce two iterated local search algorithms, a memetic algorithm with different recombination operators for the CBP and a set based neighborhood heuristic algorithm to solve the MinLA. The two iterated local search algorithms are experimentallydemonstrated to be able to compete favourably with state-of-the-art methods, the feature of a suitable crossover for the memetic algorithm is identified for the CBP and the set based neighborhood heuristic algorithm is proven to be more efficient than the traditional 2-flip neighborhood algorithm
Sun, Wen. "Heuristic Algorithms for Graph Coloring Problems." Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0027/document.
Full textThis thesis concerns four NP-hard graph coloring problems, namely, graph coloring (GCP), equitable coloring (ECP), weighted vertex coloring (WVCP) and k-vertex-critical subgraphs (k-VCS). These problems are extensively studied in the literature not only for their theoretical intractability, but also for their real-world applications in many domains. Given that they belong to the class of NP-hard problems, it is computationally difficult to solve them exactly in the general case. For this reason, this thesis is devoted to developing effective heuristic approaches to tackle these challenging problems. We develop a reduction memetic algorithm (RMA) for the graph coloring problem, a feasible and infeasible search algorithm (FISA) for the equitable coloring problem, an adaptive feasible and infeasible search algorithm (AFISA) for the weighted vertex coloring problem and an iterated backtrack-based removal (IBR) algorithm for the k-VCS problem. All these algorithms were experimentally evaluated and compared with state-of-the-art methods
Chan, Wai Hong. "Bandwidth problems of graphs." HKBU Institutional Repository, 1996. http://repository.hkbu.edu.hk/etd_ra/62.
Full textJenkins, Peter. "Partial graph design embeddings and related problems /." [St. Lucia, Qld.], 2005. http://www.library.uq.edu.au/pdfserve.php?image=thesisabs/absthe18945.pdf.
Full textLiang, Weifa, and wliang@cs anu edu au. "Designing Efficient Parallel Algorithms for Graph Problems." The Australian National University. Department of Computer Science, 1997. http://thesis.anu.edu.au./public/adt-ANU20010829.114536.
Full textDouma, Femke. "Counting and averaging problems in graph theory." Thesis, Durham University, 2010. http://etheses.dur.ac.uk/272/.
Full textChong, Ka-wong, and 莊家旺. "Improved algorithms for some classical graph problems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1996. http://hub.hku.hk/bib/B31234793.
Full textHarris, A. J. "Problems and conjectures in extremal graph theory." Thesis, University of Cambridge, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.305148.
Full textGhaffari, Mohsen. "Improved distributed algorithms for fundamental graph problems." Thesis, Massachusetts Institute of Technology, 2017. http://hdl.handle.net/1721.1/109000.
Full textCataloged from PDF version of thesis.
Includes bibliographical references (pages 237-255).
Distributed graph algorithms provide efficient and theoretically sound methods for solving graph problems in distributed settings and more generally for performing distributed computation in networks. These algorithms are applicable in a wide variety of settings, ranging from computer networks to massively parallel computing and beyond. This thesis addresses a number of the central problems of distributed graph algorithms. These problems generally revolve around two of the principal challenges of the area, locality and congestion. The problems include computing maximal independent set, minimum spanning tree, minimum edge cut and minimum vertex cut, graph connectivity decompositions, network information dissemination, minimum-weight connected dominating set, and scheduling distributed protocols. We develop novel techniques, concepts, and tools for these problems, and present algorithms and impossibility results which improve considerably on the state of the art, in several cases resolving or advancing long-standing open problems.
by Mohsen Ghaffari.
Ph. D.
Daly, Katharine M. "Hand-drawn graph problems in online education." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/100303.
Full textThis electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 104-106).
Machine-gradable assessments in online education platforms are currently limited to questions that require only keyboard or mouse input, and grading efforts generally focus only on final answers. Some types of problems in the science, technology, engineering, and math (STEM) domain, however, are most naturally answered through sketches drawn with a pen. We introduce a simple graph problem type that accepts solutions drawn using a stylus as a proof-of-concept extension to online education platforms. Simple graphs have a small number of components (vertices, arrows, and edges only), and we describe a three-step recognition process consisting of segmentation, symbol classication, and domain interpretation for converting users' pen strokes into a simple graph object representation. An experiment run on Mechanical Turk demonstrates the usability of our trained, recognition-driven drawing interface, and examples of simple graph problems illustrate how course developers can not only check students' final answers but also provide students with intermediate feedback.
by Katharine M. Daly.
M. Eng.
Pokrovskiy, Alexey. "Graph powers, partitions, and other extremal problems." Thesis, London School of Economics and Political Science (University of London), 2013. http://etheses.lse.ac.uk/754/.
Full textMa, Fuda. "Multiple Operator Metaheuristics for Graph Partitioning Problems." Thesis, Angers, 2016. http://www.theses.fr/2016ANGE0010/document.
Full textGraph partitioning problems are a class of well-known NP-hard combinatorial optimization problems with a wide range of applications, such as VLSI layout design, statistical physics, sports team scheduling, image segmentation, and protein conformation for instances. This thesis considers three representative problems in this family, including the max-k-cut problem, the max-bisection problem and the vertex separator problem (VSP). Due to high computational complexity, heuristic and metaheuristic approaches are commonly used for approximating the challenging problems. This thesis is devoted to developing efficient metaheuristic algorithms based on a collection of complementary search operators. Specifically, we develop a multiple operator heuristic (MOH) for max-k-cut, an iterated tabu search (ITS) algorithm for max-bisection and a path relinking (PR-VSP) algorithm for VSP. Extensive computational experiments and comparisons demonstrate that the proposed algorithms compete favorably with state-of-the-art approaches in the literature. The combined use of multiple search operators is analyzed to shed lights on the influence over the performance of the algorithms
Dörn, Sebastian. "Quantum complexity of graph and algebraic problems." [S.l. : s.n.], 2008. http://nbn-resolving.de/urn:nbn:de:bsz:289-vts-63034.
Full textKa-wong, Chong. "Improved algorithms for some classical graph problems /." Hong Kong : University of Hong Kong, 1996. http://sunzi.lib.hku.hk/hkuto/record.jsp?B19668508.
Full textMirghorbani, Nokandeh Seyed Mohammad S. "Graph-theoretic studies of combinatorial optimization problems." Diss., University of Iowa, 2013. https://ir.uiowa.edu/etd/4698.
Full textAncona, Bertie(Alberto). "Conditional lower bounds for graph sensitivity problems." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/123000.
Full textThesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 59-60).
In this thesis, we show conditional lower bounds for graph distance problems in the sensitivity setting, a restriction on the dynamic setting. We consider graph diameter, radius, and eccentricities over a few distance metrics, and sensitivities both constant and logarithmic in the size of the graph. Despite these restrictions, we find that many lower bound results from the static and fully dynamic settings still hold under popular conjectures. We show many of these lower bounds for graphs with constant maximum degree as well.
by Bertie Ancona.
M. Eng.
M.Eng. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science
Li, Ching-man. "Various coloring problems on plane graphs." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/hkuto/record/B39006542.
Full textLi, Ching-man, and 李靜文. "Various coloring problems on plane graphs." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B39006542.
Full textSimmons, Dayton C. (Dayton Cooper). "Applications of Rapidly Mixing Markov Chains to Problems in Graph Theory." Thesis, University of North Texas, 1993. https://digital.library.unt.edu/ark:/67531/metadc277740/.
Full textWang, Meiqiu. "Support graph preconditioning for elliptic finite element problems." [College Station, Tex. : Texas A&M University, 2008. http://hdl.handle.net/1969.1/ETD-TAMU-3135.
Full textYamaguchi, Atsuko. "Algorithms for graph theoretic optimization problems in bioinformatics." 京都大学 (Kyoto University), 2004. http://hdl.handle.net/2433/145317.
Full textZahrani, Mohammed Saeed. "Genetic local search algorithms for selected graph problems." Thesis, University of Hertfordshire, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.440188.
Full textHe, Xin. "On efficient parallel algorithms for solving graph problems /." The Ohio State University, 1987. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487331541710947.
Full textEaston, Todd William. "On partial completion problems." Diss., Georgia Institute of Technology, 1999. http://hdl.handle.net/1853/25478.
Full textGu, Guohua. "Distance-two constrained labellings of graphs and related problems." HKBU Institutional Repository, 2005. http://repository.hkbu.edu.hk/etd_ra/590.
Full textJaeger, Mordechai. "An algorithmic approach to center location and related problems." Diss., The University of Arizona, 1992. http://hdl.handle.net/10150/185767.
Full textAnnan, J. D. "The complexity of counting problems." Thesis, University of Oxford, 1994. http://ora.ox.ac.uk/objects/uuid:52070098-14fa-4cf1-ae6e-9f9ce6a626d8.
Full textHarutyunyan, Ararat. "Probabilistic methods and domination related problems in graphs." Thesis, McGill University, 2008. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=116070.
Full textWe first study alliances in graphs. There are many results in this area. For example, it is known that every connected n-vertex graph G has a global offensive alliance of size at most 2n/3. Another result is that any global defensive alliance in G has size at least ( 4n+1 - 1)/2. Our study focuses particularly on trees and algorithms for finding alliances in trees. We find the cardinality of a minimum global offensive alliance for complete k-ary trees and the minimum cardinality global defensive alliance for complete binary and ternary trees. Also, we present a linear time algorithm for finding the minimum global offensive alliance in a tree. Additionally, for a general graph, an upper bound is given on the size of a minimum global offensive alliance in terms its degree sequence. The methods that we use in this part of the thesis are mainly algorithmic and deterministic.
Then we study independent dominating sets in graphs. An independent dominating set is a set of mutually nonadjacent vertices which is also a dominating set. This is a well-studied topic (see Haynes, Hedetniemi and Slater [22]). Our main result is to show that every d-regular graph of order n with girth at least 5 and satisfying d = o(1) and d2(log d)3/2 = o(n) contains an independent dominating set of size at most (1 + o(1)) nlogdd . This generalizes the results of Duckworth and Wormald [15] for random regular graphs. We construct the independent dominating set using recent probabilistic methods which resemble Rodl's semi-random method (see for example Alon and Spencer [1]).
Finney, Andrew Martin. "The application of graph algorithms to VLSI layout." Thesis, Brunel University, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.235887.
Full textFerra, Gomes de Almeida Girão António José. "Extremal and structural problems of graphs." Thesis, University of Cambridge, 2019. https://www.repository.cam.ac.uk/handle/1810/285427.
Full textAragonès, Martín Àngels. "Graph theory applied to transmission path problems in vibroacoustics." Doctoral thesis, Universitat Ramon Llull, 2015. http://hdl.handle.net/10803/299378.
Full textA fundamental aspect when solving a vibroacoustic problem in a mechanical system is that of finding out how energy flows from a given source to any part of the system. This would help making decisions to undertake actions for diminishing, for example, the noise or vibration levels at a given system area. The dynamic behavior of a mechanical system can be estimated using different numerical methods, each of them targeting a certain frequency range. Whereas at low frequencies deterministic methods such as the Finite Element Method (FEM) or the Boundary Element Method (BEM) can be applied, statistical methods like Statistical Energy Analysis (SEA) become unavoidable at high frequencies. In addition, a large variety of approaches such as the hybrid FE-SEA, the Energy Distribution (ED) models or the Statistical modal Energy distribution Analysis (SmEdA), among many others, have been recently proposed to tackle with the so-called mid-frequency problem. However, although numerical methods can predict the pointwise or averaged vibroacoustic response of a system, they do not directly provide information on how energy flows throughout the system. Therefore, some kind of post-processing is required to determine energy transmission paths. The energy transmitted through a particular path linking a source subsystem, where external energy is being input, and a target subsystem, can be computed numerically. Yet, identifying which paths dominate the whole energy transmission from source to target usually relies on the engineer's expertise and judgement. Thus, an approach for the automatic identification of those paths would prove very useful. Graph theory provides a way out to this problem, since powerful path algorithms for graphs are available. In this thesis, a link between vibroacoustic models and graph theory is proposed, which allows one to address energy transmission path problems in a straightforward manner. The dissertation starts focusing on SEA models. It is first shown that performing a transmission path analysis (TPA) in SEA makes sense. Then a graph that accurately represents the SEA model is defined. Given that the energy transmission between sources and targets is justified by the contribution of a limited group of dominant paths in many cases of practical interest, an algorithm to find them is presented. Thereafter, an enhanced algorithm is devised to include the stochastic nature of SEA loss factors in the ranking of paths. Next, it is discussed how transmission path analysis can be extended to the mid frequency range. The graph approach for path computation becomes adapted for some ED models, as well as for SmEdA. Finally, we outline another possible application of graph theory to vibroacoustics. A graph cut algorithm strategy is implemented to achieve energy reduction at a target subsystem with the sole modification of a reduced set of loss factors. The set is found by computing cuts in the graph separating source and receiver subsystems.
Un aspecto fundamental a la hora de resolver un problema vibroacústico en un sistema mecánico es el de determinar cómo fluye la energía desde una determinada fuente hasta cualquier parte del sistema. Ello ayudaría a tomar decisiones para emprender acciones destinadas a disminuir, por ejemplo, los niveles de ruido y vibraciones en un área del sistema dada. El comportamiento dinámico de un sistema mecánico se puede estimar utilizando varios métodos numéricos, cada uno de ellos enfocado a un determinado rango de frecuencia. Mientras en las bajas frecuencias se pueden aplicar métodos deterministas como el Método de los Elementos Finitos (FEM) o el método de Elementos de Contorno (BEM), los métodos estadísticos como el Análisis Estadístico Energético son inevitables en las altas frecuencias. Además, se han desarrollado gran variedad de técnicas como el FE-SEA híbrido, los modelos de Distribución de Energía (ED) o el Análisis Estadístico de distribución de Energía modal (SmEdA), entre otras, para tratar el llamado problema de las medias frecuencias. Sin embargo, aunque los métodos numéricos pueden predecir la respuesta vibroacústica puntual o promediada de un sistema mecánico, ellos no proporcionan información sobre como fluye la energía en el sistema. Por lo tanto, hace falta algún tipo de post-procesado para determinar las vías de transmisión de energía. La energía transmitida a través de un determinado camino que conecta un subsistema fuente, donde se introduce la energía, y un subsistema receptor, se puede calcular numéricamente. A pesar de ello, identificar qué caminos dominan la transmisión de energía desde la fuente al receptor normalmente suele recaer en la experiencia o el juicio del ingeniero. Así pues, un método automático para identificar estos caminos resultaría muy útil. La teoría de grafos proporciona una solución a este problema, ya que existen potentes algoritmos de cálculos de caminos en grafos. En esta tesis, se propone un enlace entre los modelos vibroacústicos y la teoría de grafos, que permite abordar los problemas de vías de transmisión de forma directa. La disertación empieza centrándose en los modelos SEA. Primeramente, se muestra que tiene sentido realizar un análisis de vías de transmisión (TPA) en un modelo SEA. Seguidamente, se define un grafo que representa fielmente un modelo SEA. Teniendo en cuenta que en muchos casos de interés práctico, la transmisión de energía entre fuentes y receptores se puede justificar mediante la contribución de un grupo finito de vías de transmisión, se define un algoritmo para encontrarlas. A continuación, se implementa un algoritmo que incluye en el cómputo de caminos la naturaleza estocástica de los factores de pérdidas SEA. Luego, se trata la extensión del análisis de vías de transmisión al rango de media frecuencia. La técnica de teoría de grafos aplicada a cálculo de caminos se adapta para algunos modelos ED y también SmEdA. Finalmente, se presenta otra posible aplicación de la teoría de grafos a la vibroacústica. Se implementa una estrategia basada en algoritmos de cortes en grafos destinada a reducir la energía en un subsistema receptor mediante la simple modificación de un grupo reducido de factores de pérdidas. El grupo se encuentra calculando cortes que separen en el grafo los subsistemas fuentes de los subsistemas receptores.
Gellert, Laura Kristin [Verfasser]. "On problems related to graph colouring / Laura Kristin Gellert." Ulm : Universität Ulm, 2017. http://d-nb.info/1147484511/34.
Full textWu, Qinghua. "The maximum clique problems with applications to graph coloring." Angers, 2013. https://theses.hal.science/tel-01005886.
Full textThe maximum clique problem (MCP) is an important combinatorial optimization problem with a wide range of practical applications in numerous fields, including information retrieval, signal transmission analysis, classification theory, economics, scheduling, and biomedical engineering. Moreover, a number of combinatorial optimization problems are tightly related to MCP, such as graph coloring, sum coloring, set packing and optimal winner determination. This thesis is devoted to developing effective heuristic approaches to tackle the maximum clique problem and its generalizations. To achieve this, we developed an adaptive multistart tabu search approach for the classic maximum clique problem, a multi-neighborhood tabu search algorithm for the maximum vertex weight clique and a hybrid metaheuristic method for the maximum edge weight clique problem. Moreover, we apply these developed heuristic approaches to solve these hard problems which are tightly related to the maximum clique problem. All algorithms are implemented and successfully tested on a number of benchmark instances from diverse application areas. The proposed methods favorably compete with other state-of-art approaches
Fischer, Thomas. "Distributed memetic algorithms for graph theoretical combinatorial optimization problems." Berlin Logos-Verl, 2008. http://d-nb.info/994066945/04.
Full textLignos, Ioannis. "Reconfigurations of combinatorial problems : graph colouring and Hamiltonian cycle." Thesis, Durham University, 2017. http://etheses.dur.ac.uk/12098/.
Full textChase, Melissa. "Shortest Path Problems: Multiple Paths in a Stochastic Graph." Scholarship @ Claremont, 2003. https://scholarship.claremont.edu/hmc_theses/143.
Full text