To see the other types of publications on this topic, follow the link: Graph covering.
Dissertations / Theses on the topic 'Graph covering'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 43 dissertations / theses for your research on the topic 'Graph covering.'
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.
1
Bryant, Roy Dale. "Covering the de Bruijn graph." Thesis, Monterey, California. Naval Postgraduate School, 1986. http://hdl.handle.net/10945/21751.
Full textAbstract:
Random-like sequences of 0's and l's are generated efficiently by binary shift registers. The output of n-stage shift registers viewed as a sequence of binary n-tuples also give rise to a special graph called the de Bruijn graph B . The de Bruijn graph is a directed graph with 2n nodes. Each node has 2 arcs entering it and 2 arcs going out of it. Thus, there are a total of 2n+1 arcs in Bn. In this thesis, we define a cover of the de Bruijn graph, different from the usual graph theoretic cover. A cover S of the de Bruijn graph is defined as an independent subset of the nodes of Bn that satisfy the following J property. For each node x in Bn - S, there exists a node y in S such that either the arc
2
Maltais, Elizabeth Jane. "Graph-dependent Covering Arrays and LYM Inequalities." Thesis, Université d'Ottawa / University of Ottawa, 2016. http://hdl.handle.net/10393/34434.
Full textAbstract:
The problems we study in this thesis are all related to covering arrays.
Covering arrays are combinatorial designs, widely used as templates for efficient interaction-testing suites. They have connections to many areas including extremal set theory, design theory, and graph theory.
We define and study several generalizations of covering arrays, and we develop a method which produces an infinite family of LYM inequalities for graph-intersecting collections.
A common theme throughout is the dependence of these problems on graphs.
Our main contribution is an extremal method yielding LYM inequalities for $H$-intersecting collections, for every undirected graph $H$. Briefly, an $H$-intersecting collection is a collection of packings (or partitions) of an $n$-set in which the classes of every two distinct packings in the collection intersect according to the edges of $H$.
We define ``$F$-following" collections which, by definition, satisfy a LYM-like inequality that depends on the arcs of a ``follow" digraph $F$ and a permutation-counting technique. We fully characterize the correspondence between ``$F$-following" and ``$H$-intersecting" collections. This enables us to apply our inequalities to $H$-intersecting collections.
For each graph $H$, the corresponding inequality inherently bounds the maximum number of columns in a covering array with alphabet graph $H$.
We use this feature to derive bounds for covering arrays with the alphabet graphs $S_3$ (the star on three vertices) and $\kvloop{3}$ ($K_3$ with loops). The latter improves a known bound for classical covering arrays of strength two.
We define covering arrays on column graphs and alphabet graphs which generalize covering arrays on graphs. The column graph encodes which pairs of columns must be $H$-intersecting, where $H$ is a given alphabet graph. Optimizing covering arrays on column graphs and alphabet graphs is equivalent to a graph-homomorphism problem
to a suitable family of targets which generalize qualitative independence graphs. When $H$ is the two-vertex tournament, we give constructions and bounds for covering arrays on directed column graphs.
FOR arrays are the broadest generalization of covering arrays that we consider. We define FOR arrays to encompass testing applications where constraints must be considered, leading to forbidden, optional, and required interactions of any strength.
We model these testing problems using a hypergraph. We investigate the existence of FOR arrays, the compatibility of their required interactions, critical systems, and binary relational systems that model the problem using homomorphisms.
3
Minei, Marvin. "Three block diagonalization methods for the finite Cayley and covering graph /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2000. http://wwwlib.umi.com/cr/ucsd/fullcit?p9974107.
Full text
4
Tanaka, Ryokichi. "Large deviation on a covering graph with group of polynomial growth." 京都大学 (Kyoto University), 2012. http://hdl.handle.net/2433/152534.
Full text
5
Yu, Nuo 1983. "Fixed parameter tractable algorithms for optimal covering tours with turns." Thesis, McGill University, 2008. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=111595.
Full textAbstract:
Many geometry problems can be solved by transformation to graph problems. Often, both the geometry version and graph version of the problem are NP-hard - and therefore not likely to be solved in polynomial time. One approach to solving these hard problems is to use fixed parameter tractable (FPT) algorithms. We present a framework for developing FPT algorithms for graph problems using dynamic programming, monadic second order logic of graphs, tree-width, and bidimensionality. We use this framework to obtain FPT results for covering tour problems on grid-graphs with turn costs. The results for these problems are not practical, but they demonstrate how the basic framework can be used to quickly obtain FPT results. We provide suggestions on further research to improve our FPT results and to apply our framework to obtain new FPT results.
6
許眞眞 and Zhenzhen Xu. "A min-max theorem on packing and covering cycles in graphs." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2002. http://hub.hku.hk/bib/B31226966.
Full text
7
Xu, Zhenzhen. "A min-max theorem on packing and covering cycles in graphs /." Hong Kong : University of Hong Kong, 2002. http://sunzi.lib.hku.hk/hkuto/record.jsp?B25155301.
Full text
8
Gibbins, Aliska L. "Automorphism Groups of Buildings Constructed Via Covering Spaces." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1373976456.
Full text
9
Levy, Eythan. "Approximation algorithms for covering problems in dense graphs." Doctoral thesis, Universite Libre de Bruxelles, 2009. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210359.
Full textAbstract:
We present a set of approximation results for several covering problems in dense graphs. These results show that for several problems, classical algorithms with constant approximation ratios can be analyzed in a finer way, and provide better constant approximation ratios under some density constraints. In particular, we show that the maximal matching heuristic approximates VERTEX COVER (VC) and MINIMUM MAXIMAL MATCHING (MMM) with a constant ratio strictly smaller than 2 when the proportion of edges present in the graph (weak density) is at least 3/4, or when the normalized minimum degree (strong density) is at least 1/2. We also show that this result can be improved by a greedy algorithm which provides a constant ratio smaller than 2 when the weak density is at least 1/2. We also provide tight families of graphs for all these approximation ratios. We then looked at several algorithms from the literature for VC and SET COVER (SC). We present a unified and critical approach to the Karpinski/Zelikovsky, Imamura/Iwama and Bar-Yehuda/Kehat algorithms, identifying the general the general scheme underlying these algorithms.Finally, we look at the CONNECTED VERTEX COVER (CVC) problem,for which we proposed new approximation results in dense graphs. We first analyze Carla Savage's algorithm, then a new variant of the Karpinski-Zelikovsky algorithm. Our results show that these algorithms provide the same approximation ratios for CVC as the maximal matching heuristic and the Karpinski-Zelikovsky algorithm did for VC. We provide tight examples for the ratios guaranteed by both algorithms. We also introduce a new invariant, the "price of connectivity of VC", defined as the ratio between the optimal solutions of CVC and VC, and showed a nearly tight upper bound on its value as a function of the weak density. Our last chapter discusses software aspects, and presents the use of the GRAPHEDRON software in the framework of approximation algorithms, as well as our contributions to the development of this system.
/
Nous présentons un ensemble de résultats d'approximation pour plusieurs problèmes de couverture dans les graphes denses. Ces résultats montrent que pour plusieurs problèmes, des algorithmes classiques à facteur d'approximation constant peuvent être analysés de manière plus fine, et garantissent de meilleurs facteurs d'aproximation constants sous certaines contraintes de densité. Nous montrons en particulier que l'heuristique du matching maximal approxime les problèmes VERTEX COVER (VC) et MINIMUM MAXIMAL MATCHING (MMM) avec un facteur constant inférieur à 2 quand la proportion d'arêtes présentes dans le graphe (densité faible) est supérieure à 3/4 ou quand le degré minimum normalisé (densité forte) est supérieur à 1/2. Nous montrons également que ce résultat peut être amélioré par un algorithme de type GREEDY, qui fournit un facteur constant inférieur à 2 pour des densités faibles supérieures à 1/2. Nous donnons également des familles de graphes extrémaux pour nos facteurs d'approximation. Nous nous somme ensuite intéressés à plusieurs algorithmes de la littérature pour les problèmes VC et SET COVER (SC). Nous avons présenté une approche unifiée et critique des algorithmes de Karpinski-Zelikovsky, Imamura-Iwama, et Bar-Yehuda-Kehat, identifiant un schéma général dans lequel s'intègrent ces algorithmes.
Nous nous sommes finalement intéressés au problème CONNECTED VERTEX COVER (CVC), pour lequel nous avons proposé de nouveaux résultats d'approximation dans les graphes denses, au travers de l'algorithme de Carla Savage d'une part, et d'une nouvelle variante de l'algorithme de Karpinski-Zelikovsky d'autre part. Ces résultats montrent que nous pouvons obtenir pour CVC les mêmes facteurs d'approximation que ceux obtenus pour VC à l'aide de l'heuristique du matching maximal et de l'algorithme de Karpinski-Zelikovsky. Nous montrons également des familles de graphes extrémaux pour les ratios garantis par ces deux algorithmes. Nous avons également étudié un nouvel invariant, le coût de connectivité de VC, défini comme le rapport entre les solutions optimales de CVC et de VC, et montré une borne supérieure sur sa valeur en fonction de la densité faible. Notre dernier chapitre discute d'aspects logiciels, et présente l'utilisation du logiciel GRAPHEDRON dans le cadre des algorithmes d'approximation, ainsi que nos contributions au développement du logiciel.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
10
El-Darzi, E. "Methods for solving the set covering and set partitioning problems using graph theoretic (relaxation) algorithms." Thesis, Brunel University, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.381678.
Full text
11
Sabbir, Tarikul Alam Khan. "Topology sensitive algorithms for large scale uncapacitated covering problem." Thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2011, 2011. http://hdl.handle.net/10133/3235.
Full textAbstract:
Solving NP-hard facility location problems in wireless network planning is a common scenario.
In our research, we study the Covering problem, a well known facility location problem with applications
in wireless network deployment. We focus on networks with a sparse structure. First,
we analyzed two heuristics of building Tree Decomposition based on vertex separator and perfect
elimination order. We extended the vertex separator heuristic to improve its time performance. Second,
we propose a dynamic programming algorithm based on the Tree Decomposition to solve the
Covering problem optimally on the network. We developed several heuristic techniques to speed
up the algorithm. Experiment results show that one variant of the dynamic programming algorithm
surpasses the performance of the state of the art mathematical optimization commercial software on
several occasions.ix, 89 leaves : ill. ; 29 cm
12
Akhoondian, Amiri Saeed [Verfasser], Stephan [Akademischer Betreuer] Kreutzer, Stephan [Gutachter] Kreutzer, Marcin [Gutachter] Pilipczuk, and Dimitrios [Gutachter] Thilikos. "Structural graph theory meets algorithms: covering and connectivity problems in graphs / Saeed Akhoondian Amiri ; Gutachter: Stephan Kreutzer, Marcin Pilipczuk, Dimitrios Thilikos ; Betreuer: Stephan Kreutzer." Berlin : Technische Universität Berlin, 2017. http://d-nb.info/1156182174/34.
Full text
13
Xia, Yan. "Packings and Coverings of Complete Graphs with a Hole with the 4-Cycle with a Pendant Edge." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/etd/1173.
Full textAbstract:
In this thesis, we consider packings and coverings of various complete graphs with the 4-cycle with a pendant edge. We consider both restricted and unrestricted coverings. Necessary and sufficient conditions are given for such structures for (1) complete graphs Kv, (2) complete bipartite graphs Km,n, and (3) complete graphs with a hole K(v,w).
14
Hellmuth, Marc. "Local Prime Factor Decomposition of Approximate Strong Product Graphs." Doctoral thesis, Universitätsbibliothek Leipzig, 2010. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-38755.
Full textAbstract:
In practice, graphs often occur as perturbed product structures, so-called approximate graph products. The practical application of the well-known prime factorization algorithms is therefore limited, since
most graphs are prime, although they can have a product-like structure.
This work is concerned with the strong graph product. Since strong product graphs G contain
subgraphs that are itself products of subgraphs of the underlying factors of G, we follow the idea to
develop local approaches that cover a graph by factorizable patches and then use this information to
derive the global factors.
First, we investigate the local structure of strong product graphs and introduce the backbone B(G)
of a graph G and the so-called S1-condition. Both concepts play a central role for determining the
prime factors of a strong product graph in a unique way. Then, we discuss several graph classes,
in detail, NICE, CHIC and locally unrefined graphs. For each class we construct local, quasi-linear
time prime factorization algorithms. Combining these results, we then derive a new local prime
factorization algorithm for all graphs.
Finally, we discuss approximate graph products. We use the new local factorization algorithm to
derive a method for the recognition of approximate graph products. Furthermore, we evaluate the
performance of this algorithm on a sample of approximate graph products.
15
Vandomme, Elise. "Contributions to combinatorics on words in an abelian context and covering problems in graphs." Thesis, Université Grenoble Alpes (ComUE), 2015. http://www.theses.fr/2015GRENM010/document.
Full textAbstract:
Cette dissertation se divise en deux parties, distinctes mais connexes, qui sont le reflet de la cotutelle. Nous étudions et résolvons des problèmes concernant d'une part la combinatoire des mots dans un contexte abélien et d'autre part des problèmes de couverture dans des graphes. Chaque question fait l'objet d'un chapitre. En combinatoire des mots, le premier problème considéré s'intéresse à la régularité des suites au sens défini par Allouche et Shallit. Nous montrons qu'une suite qui satisfait une certaine propriété de symétrie est 2-régulière. Ensuite, nous appliquons ce théorème pour montrer que les fonctions de complexité 2-abélienne du mot de Thue--Morse ainsi que du mot appelé ''period-doubling'' sont 2-régulières. Les calculs et arguments développés dans ces démonstrations s'inscrivent dans un schéma plus général que nous espérons pouvoir utiliser à nouveau pour prouver d'autres résultats de régularité. Le deuxième problème poursuit le développement de la notion de mot de retour abélien introduite par Puzynina et Zamboni. Nous obtenons une caractérisation des mots sturmiens avec un intercepte non nul en termes du cardinal (fini ou non) de l'ensemble des mots de retour abélien par rapport à tous les préfixes. Nous décrivons cet ensemble pour Fibonacci ainsi que pour Thue--Morse (bien que cela ne soit pas un mot sturmien). Nous étudions la relation existante entre la complexité abélienne et le cardinal de cet ensemble. En théorie des graphes, le premier problème considéré traite des codes identifiants dans les graphes. Ces codes ont été introduits par Karpovsky, Chakrabarty et Levitin pour modéliser un problème de détection de défaillance dans des réseaux multiprocesseurs. Le rapport entre la taille optimale d'un code identifiant et la taille optimale du relâchement fractionnaire d'un code identifiant est comprise entre 1 et 2 ln(|V|)+1 où V est l'ensemble des sommets du graphe. Nous nous concentrons sur les graphes sommet-transitifs, car nous pouvons y calculer précisément la solution fractionnaire. Nous exhibons des familles infinies, appelées quadrangles généralisés, de graphes sommet-transitifs pour lesquelles les solutions entière et fractionnaire sont de l'ordre |V|^k avec k dans {1/4, 1/3, 2/5}. Le second problème concerne les (r,a,b)-codes couvrants de la grille infinie déjà étudiés par Axenovich et Puzynina. Nous introduisons la notion de 2-coloriages constants de graphes pondérés et nous les étudions dans le cas de quatre cycles pondérés particuliers. Nous présentons une méthode permettant de lier ces 2-coloriages aux codes couvrants. Enfin, nous déterminons les valeurs exactes des constantes a et b de tout (r,a,b)-code couvrant de la grille infinie avec |a-b|>4. Il s'agit d'une extension d'un théorème d'AxenovichThis dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter. In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence satisfying a certain symmetry property is 2-regular. Then we apply this theorem to show that the 2-abelian complexity functions of the Thue--Morse word and the period-doubling word are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results. The second question concerns the notion of return words up to abelian equivalence, introduced by Puzynina and Zamboni. We obtain a characterization of Sturmian words with non-zero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the Thue-Morse word (which is not Sturmian). We investigate the relationship existing between the abelian complexity and the finiteness of this set. In graph theory, the first problem considered deals with identifying codes in graphs. These codes were introduced by Karpovsky, Chakrabarty and Levitin to model fault-diagnosis in multiprocessor systems. The ratio between the optimal size of an identifying code and the optimal size of a fractional relaxation of an identifying code is between 1 and 2 ln(|V|)+1 where V is the vertex set of the graph. We focus on vertex-transitive graphs, since we can compute the exact fractional solution for them. We exhibit infinite families, called generalized quadrangles, of vertex-transitive graphs with integer and fractional identifying codes of order |V|^k with k in {1/4,1/3,2/5}. The second problem concerns (r,a,b)-covering codes of the infinite grid already studied by Axenovich and Puzynina. We introduce the notion of constant 2-labellings of weighted graphs and study them in four particular weighted cycles. We present a method to link these labellings with covering codes. Finally, we determine the precise values of the constants a and b of any (r,a,b)-covering code of the infinite grid with |a-b|>4. This is an extension of a theorem of Axenovich
16
Freitas, Lucas Ismaily Bezerra 1987. "A conjectura de Tuza sobre triângulos em grafos." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275522.
Full textAbstract:
Orientador: Orlando LeeDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-25T17:05:58Z (GMT). No. of bitstreams: 1 Freitas_LucasIsmailyBezerra_M.pdf: 2067916 bytes, checksum: 77f11deab9d862fe9a10de2df94b447c (MD5) Previous issue date: 2014
Resumo: Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação, nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contra-exemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K_5
Abstract: In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza's conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K_5 minor
Mestrado
Ciência da Computação
Mestre em Ciência da Computação
17
Sheppard, Nicholas Paul. "Self-Reduction for Combinatorial Optimisation." University of Sydney. Computer Science, 2001. http://hdl.handle.net/2123/797.
Full textAbstract:
This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.
18
Raspaud, André. "Flots et couvertures par des cycles dans les graphes et les matroïdes." Phd thesis, Grenoble 1, 1985. http://tel.archives-ouvertes.fr/tel-00316071.
Full textAbstract:
Introduction. Couvertures des graphes par des cycles. Couverture par des circuits d'un matroïde régulier qui admet un Z.5- flot non nul. Flots de Fulkerson. Flots de Petersen. Constructions locales. Annexe. Bibliographie
19
Muller, Carole. "Minor-closed classes of graphs: Isometric embeddings, cut dominants and ball packings." Doctoral thesis, Universite Libre de Bruxelles, 2021. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/331629.
Full textAbstract:
Une classe de graphes est close par mineurs si, pour tout graphe dans la classe et tout mineur de ce graphe, le mineur est ́egalement dans la classe. Par un fameux th ́eor`eme de Robertson et Seymour, nous savons que car- act ́eriser une telle classe peut ˆetre fait `a l’aide d’un nombre fini de mineurs exclus minimaux. Ceux-ci sont des graphes qui n’appartiennent pas `a la classe et qui sont minimaux dans le sens des mineurs pour cette propri ́et ́e.Dans cette thèse, nous étudions trois problèmes à propos de classes de graphes closes par mineurs. Les deux premiers sont reliés à la caractérisation de certaines classes de graphes, alors que le troisième étudie une relation de “packing-covering” dans des graphes excluant un mineur.Pour le premier problème, nous étudions des plongements isométriques de graphes dont les arêtes sont pondérées dans des espaces métriques. Principalement, nous nous intêressons aux espaces ell_2 et ell_∞. E ́tant donné un graphe pondéré, un plongement isométrique associe à chaque sommet du graphe un vecteur dans l’autre espace de sorte que pour chaque arête du graphe le poids de celle-ci est égal à la distance entre les vecteurs correspondant à ses sommets. Nous disons qu’une fonction de poids sur les arêtes est une fonction de distances réalisable s’il existe un tel plongement. Le paramètre f_p(G) détermine la dimension k minimale d’un espace ell_p telle que toute fonction de distances réalisable de G peut être plongée dans ell_p^k. Ce paramètre est monotone dans le sens des mineurs. Nous caractérisons les graphes tels que f_p(G) a une grande valeur en termes de mineurs inévitables pour p = 2 et p = ∞. Une famille de graphes donne des mineurs inévitables pour un invariant monotone pour les mineurs, si ces graphes “expliquent” pourquoi l’invariant est grand.Le deuxième problème étudie les mineurs exclus minimaux pour la classe de graphes avec φ(G) borné par une constante k, où φ(G) est un paramètre lié au dominant des coupes d’un graphe G. Ce polyèdre contient tous les points qui, composante par composante, sont plus grands ou égaux à une combination convexe des vecteurs d’incidence de coupes dans G. Le paramètre φ(G) est égal au membre de droite maximum d’une description linéaire du dominant des coupes de G en forme entière minimale. Nous étudions les mineurs exclus minimaux pour la propriété φ(G) <= 4 et montrons une nouvelle borne sur φ(G) en termes du “vertex cover number”.Le dernier problème est d’un autre type. Nous étudions une relation de “packing-covering” dans les classes de graphes excluant un mineur. Étant donné un graphe G, une boule de centre v et de rayon r est l’ensemble de tous les sommets de G qui sont à distance au plus r de v. Pour un graphe G et une collection de boules donnés nous pouvons définir un hypergraphe H dont les sommets sont ceux de G et les arêtes correspondent aux boules de la collection. Il est bien connu que dans l’hypergraphe H, le “transversal number” τ(H) vaut au moins le “packing number” ν(H). Nous montrons une borne supérieure sur ν(H) qui est linéaire en τ(H), résolvant ainsi un problème ouvert de Chepoi, Estellon et Vaxès.A class of graphs is closed under taking minors if for each graph in the class and each minor of this graph, the minor is also in the class. By a famous result of Robertson and Seymour, we know that characterizing such a class can be done by identifying a finite set of minimal excluded minors, that is, graphs which do not belong to the class and are minor-minimal for this property.In this thesis, we study three problems in minor-closed classes of graphs. The first two are related to the characterization of some graph classes, while the third one studies a packing-covering relation for graphs excluding a minor.In the first problem, we study isometric embeddings of edge-weighted graphs into metric spaces. In particular, we consider ell_2- and ell_∞-spaces. Given a weighted graph, an isometric embedding maps the vertices of this graph to vectors such that for each edge of the graph the weight of the edge equals the distance between the vectors representing its ends. We say that a weight function on the edges of the graph is a realizable distance function if such an embedding exists. The minor-monotone parameter f_p(G) determines the minimum dimension k of an ell_p-space such that any realizable distance function of G is realizable in ell_p^k. We characterize graphs with large f_p(G) value in terms of unavoidable minors for p = 2 and p = ∞. Roughly speaking, a family of graphs gives unavoidable minors for a minor-monotone parameter if these graphs “explain” why the parameter is high.The second problem studies the minimal excluded minors of the class of graphs such that φ(G) is bounded by some constant k, where φ(G) is a parameter related to the cut dominant of a graph G. This unbounded polyhedron contains all points that are componentwise larger than or equal to a convex combination of incidence vectors of cuts in G. The parameter φ(G) is equal to the maximum right-hand side of a facet-defining inequality of the cut dominant of G in minimum integer form. We study minimal excluded graphs for the property φ(G) <= 4 and provide also a new bound of φ(G) in terms of the vertex cover number.The last problem has a different flavor as it studies a packing-covering relation in classes of graphs excluding a minor. Given a graph G, a ball of center v and radius r is the set of all vertices in G that are at distance at most r from v. Given a graph and a collection of balls, we can define a hypergraph H such that its vertices are the vertices of G and its edges correspond to the balls in the collection. It is well-known that, in the hypergraph H, the transversal number τ(H) is at least the packing number ν(H). We show that we can bound τ(H) from above by a linear function of ν(H) for every graphs G and ball collections H if the graph G excludes a minor, solving an open problem by Chepoi, Estellon et Vaxès.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
20
Imbert, Michel. "Combinatoire des revêtements : cellulation des espaces de Hurwitz." Université Joseph Fourier (Grenoble), 1998. http://www.theses.fr/1998GRE10228.
Full textAbstract:
L'objet de cette these est l'etude combinatoire des revetements entre surfaces de riemann et de leurs espaces modulaires : les espaces de hurwitz. Les methodes utilisees sont graphiques : nous utilisons largement le concept de graphe epais. Nous donnons un algorithme de calcul des lacets d'homologie d'un tel graphe. Nous montrons le theoreme d'existence de riemann au niveau des graphes epais. Nous detaillons le processus, du a j. L. Harer et m. Kontsevich, realisant un graphe epais a n faces muni de longueurs d'aretes en une surface de riemann compacte privee de n piqures. Ce processus, bijectif par le theoreme de strebel, mene a une decomposition cellulaire connue et fondamentale des espaces de modules de surfaces de riemann compactes de genre fixe et privees de n piqures. Nous sommes alors en mesure de preciser la variation de la structure complexe en fonction des longueurs d'aretes (ce qui donne la continuite du processus), et de generaliser le processus aux revetements de surfaces de riemann compactes. Cela conduit a la decomposition cellulaire des espaces de hurwitz. Nous etudions un exemple ou l'espace de hurwitz s'identifie a une courbe modulaire. L'etude des revetements cycliques des tores permet de relier l'espace de hurwitz correspondant a des espaces de modules definis par e. Witten dans le cadre d'une conjecture generalisant celle demontree par m. Kontsevich. L'extension des resultats aux compactifications des espaces de modules et de hurwitz s'appuie sur le phenomene de retraction de boucles d'un graphe epais ne bordant pas des faces.
21
Wagner, Andrew. "Eulerian Properties of Design Hypergraphs and Hypergraphs with Small Edge Cuts." Thesis, Université d'Ottawa / University of Ottawa, 2019. http://hdl.handle.net/10393/39092.
Full textAbstract:
An Euler tour of a hypergraph is a closed walk that traverses every edge exactly once; if a hypergraph admits such a walk, then it is called eulerian. Although this notion is one of the progenitors of graph theory --- dating back to the eighteenth century --- treatment of this subject has only begun on hypergraphs in the last decade. Other authors have produced results about rank-2 universal cycles and 1-overlap cycles, which are equivalent to our definition of Euler tours.
In contrast, an Euler family is a collection of nontrivial closed walks that jointly traverse every edge of the hypergraph exactly once and cannot be concatenated simply. Since an Euler tour is an Euler family comprising a single walk, having an Euler family is a weaker attribute than being eulerian; we call a hypergraph quasi-eulerian if it admits an Euler family. Due to a result of Lovász, it can be much easier to determine that some classes of hypergraphs are quasi-eulerian, rather than eulerian; in this thesis, we present some techniques that allow us to make the leap from quasi-eulerian to eulerian.
A triple system of order n and index λ (denoted TS(n,λ)) is a 3-uniform hypergraph in which every pair of vertices lies together in exactly λ edges. A Steiner triple system of order n is a TS(n,1). We first give a proof that every TS(n,λ) with λ ⩾ 2 is eulerian. Other authors have already shown that every such triple system is quasi-eulerian, so we modify an Euler family in order to show that an Euler tour must exist. We then give a proof that every Steiner triple system (barring the degenerate TS(3,1)) is eulerian. We achieve this by first constructing a near-Hamilton cycle out of some of the edges, then demonstrating that the hypergraph consisting of the remaining edges has a decomposition into closed walks in which each edge is traversed exactly once.
In order to extend these results on triple systems, we define a type of hypergraph called an ℓ-covering k-hypergraph, a k-uniform hypergraph in which every ℓ-subset of the vertices lie together in at least one edge. We generalize the techniques used earlier on TS(n,λ) with λ ⩾ 2 and define interchanging cycles. Such cycles allow us to transform an Euler family into another Euler family, preferably of smaller cardinality. We first prove that all 2-covering 3-hypergraphs are eulerian by starting with an Euler family that has the minimum cardinality possible, then demonstrating that if there are two or more walks in the Euler family, then we can rework two or more of them into a single walk. We then use this result to prove by induction that, for k ⩾ 3, all (k-1)-covering k-hypergraphs are eulerian.
We attempt to extend these results further to all ℓ-covering k-hypergraphs for ℓ ⩾ 2 and k ⩾ 3. Using the same induction technique as before, we only need to give a result for 2-covering k-hypergraphs. We are able to use Lovász's condition and some counting techniques to show that these are all quasi-eulerian.
Finally, we give some constructive results on hypergraphs with small edge cuts. There has been analogous work by other authors on hypergraphs with small vertex cuts. We reduce the problem of finding an Euler tour in a hypergraph to finding an Euler tour in each of the connected components of the edge-deleted subhypergraph, then show how these individual Euler tours can be concatenated.
22
Sbihi, Amine M. (Amine Mohammed). "Covering times for random walks on graphs." Thesis, McGill University, 1990. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=74538.
Full textAbstract:
This thesis is a contribution to the covering times problems for random walks on graphs. By considering uniform random walks on finite connected graphs, the covering time is defined as the time (number of steps) taken by the random walk to visit every vertex. The motivating problem of this thesis is to find bounds for the expected covering times. We provide explicit bounds that are uniformly valid over all starting points and over large classes of graphs. In some cases the asymptotic distribution of the suitably normalized covering time is given as well.
23
Meagher, Karen. "Covering arrays on graphs: Qualitative independence graphs and extremal set partition theory." Thesis, University of Ottawa (Canada), 2005. http://hdl.handle.net/10393/29234.
Full textAbstract:
There has been a good deal of research on covering arrays over the last 20 years. Most of this work has focused on constructions, applications and generalizations of covering arrays. The main focus of this thesis is a generalization of covering arrays, covering arrays on graphs. The original motivation for this generalization was to improve applications of covering arrays to testing systems and networks, but this extension also gives us new ways to study covering arrays.
Two vectors v, w in Znk are qualitatively independent if for all ordered pairs (a, b) ∈ Zk x Zk there is a position i in the vectors where ( a, b) = (vi, w i). A covering array is an array with the property that any pair of rows are qualitatively independent. A covering array on a graph is an array with a row for each vertex of the graph with the property that any two rows which correspond to adjacent vertices are qualitatively independent. A covering array on the complete graph is a covering array. A covering array is optimal if it has the minimum number of columns among covering arrays with the same number of rows.
The addition of a graph structure to covering arrays makes it possible to use methods from graph theory to study these designs. In this thesis, we define a family of graphs called the qualitative independence graphs . A graph has a covering array, with given parameters, if and only if there is a homomorphism from the graph to a particular qualitative independence graph. Cliques in qualitative independence graphs relate to covering arrays and independent sets are connected to intersecting partition systems.
It is known that the exact size of an optimal binary covering array can be determined using Sperner's Theorem and the Erdős-Ko-Rado Theorem. In this thesis, we find good bounds on the size of an optimal binary covering array on a graph. In addition, we determine both the chromatic number and a core of the binary qualitative independence graphs. Since the rows of general covering arrays correspond to set partitions, we give extensions of Sperner's Theorem and the Erdős-Ko-Rado Theorem to set-partition systems. These results are part of a general framework to study extremal partition systems.
The core of the binary qualitative independence graphs can be generalized to a subgraph of a general qualitative independence graph called the uniform qualitative independence graph. Cliques in the uniform qualitative independence graphs relate to balanced covering arrays. Using these graphs, we find bounds on the size of a balanced covering array. We give the spectra for several of these graphs and conjecture that they are graphs in an association scheme.
We also give a new construction for covering arrays which yields many new upper bounds on the size of optimal covering arrays.
24
Zekaoui, Latifa. "Mixed covering arrays on graphs and tabu search algorithms." Thesis, University of Ottawa (Canada), 2006. http://hdl.handle.net/10393/27433.
Full textAbstract:
Covering arrays are combinatorial objects that have been successfully applied in the design of test suits for testing software, networks and circuits. Mixed covering arrays on graphs are new generalizations of both mixed covering arrays and covering arrays on graphs.
In this thesis, we give new theoretical results and constructions for mixed covering arrays on graphs. First, we extend to the mixed case the work done by Meagher and Stevens [31], which uses graph homomorphisms for covering arrays on graphs. Second, we study covering arrays on special classes of graphs. In particular, we solve to optimality the case in which G is a tree, a cycle or a bipartite graph, as well as give results for wheels and cubic graphs. We also provide general graph operations that preserve the size of a balanced covering array.
In the second part of the thesis, we do a complete experimental study of two tabu search algorithms for covering array construction. POT is a variation of the algorithm given by Stardom [40] while PAT is an implementation of the algorithm proposed by Nurmela [35]. We conclude that they provide effective methods for constructing covering arrays of moderate size. In particular, POT and PAT improve upper bounds for 18 sets of parameters for covering arrays.
25
Hur, Suhkjin. "The Kuratowski covering conjecture for graphs of order less than 10." Columbus, Ohio : Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1209141894.
Full text
26
Shumway, Alexander Jin. "Adding Limit Points to Bass-Serre Graphs of Groups." BYU ScholarsArchive, 2018. https://scholarsarchive.byu.edu/etd/6954.
Full textAbstract:
We give a brief overview of Bass-Serre theory and introduce a method of adding a limit point to graphs of groups. We explore a basic example of this method, and find that while the fundamental theorem of Bass-Serre theory no longer applies in this case we still recover a group action on a covering space of sorts with a subgroup isomorphic to the fundamental group of our new base space with added limit point. We also quantify how much larger the fundamental group of a graph of groups becomes after this construction, and discuss the effects of adding and identifying together such limit points in more general graphs of groups. We conclude with a theorem stating that the cokernel of the map on fundamental groups induced by collapsing an arc between two limit points contains a certain fundamental group of a double cone of graphs of groups, and we conjecture that this cokernel is isomorphic to this double cone group.
27
Surber, Wesley M. "Restricted and Unrestricted Coverings of Complete Bipartite Graphs with Hexagons." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/etd/1136.
Full textAbstract:
A minimal covering of a graph G with isomorphic copies of graph H is a set {H1, H2, H3, ... , Hn} where Hi is isomorphic to H, the vertex set of Hi is a subset of G, the edge set of G is a subset of the union of Hi's, and the cardinality of the union of Hi's minus G is minimum. Some studies have been made of covering the complete graph in which case an added condition of the edge set of Hi is the subset of the edge set of G for all i which implies no additional restrictions. However, if G is not the complete graph, then this condition may have implications. We will give necessary and sufficient conditions for minimal coverings of complete bipartite graph with 6-cycles, which we call minimal unrestricted coverings. We also give necessary and sufficient conditions for minimal coverings of the complete bipartite graph with 6-cycles with the added condition the edge set of Hi is a subset of G for all i, and call these minimal restricted coverings.
28
Issac, Davis [Verfasser], and Andreas [Akademischer Betreuer] Karrenbauer. "On some covering, partition and connectivity problems in graphs / Davis Issac ; Betreuer: Andreas Karrenbauer." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2019. http://d-nb.info/1196621233/34.
Full text
29
Issac, Davis Verfasser], and Andreas [Akademischer Betreuer] [Karrenbauer. "On some covering, partition and connectivity problems in graphs / Davis Issac ; Betreuer: Andreas Karrenbauer." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2019. http://d-nb.info/1196621233/34.
Full text
30
Hägglund, Jonas. "Snarks : Generation, coverings and colourings." Doctoral thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-53337.
Full textAbstract:
For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis. The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order. In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24. In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs. In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings. Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.
31
Cooper, Melody Elaine. "Packings and Coverings of Various Complete Digraphs with the Orientations of a 4-Cycle." Digital Commons @ East Tennessee State University, 2007. https://dc.etsu.edu/etd/2031.
Full textAbstract:
There are four orientations of cycles on four vertices. Necessary and sufficient conditions are given for covering complete directed digraphs Dv, packing and covering complete bipartite digraphs, Dm,n, and packing and covering the complete digraph on v vertices with hole of size w, D(v,w), with three of the orientations of a 4-cycle, including C4, X, and Y.
32
Henack, Eric [Verfasser]. "Separability Properties and Finite-Sheeted Coverings of Graphs of Groups and 2-dimensional Orbifolds / Eric Henack." Kiel : Universitätsbibliothek Kiel, 2018. http://d-nb.info/115626443X/34.
Full text
33
Cantrell, Daniel Shelton. "Cyclic, f-Cyclic, and Bicyclic Decompositions of the Complete Graph into the 4-Cycle with a Pendant Edge." Digital Commons @ East Tennessee State University, 2009. https://dc.etsu.edu/etd/1872.
Full textAbstract:
In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of:
(1) a single cycle of length v,
(2) f fixed points and a cycle of length v − f, or
(3) two disjoint cycles.
The purpose of this thesis is to give necessary and sufficient conditions for the existence of cyclic, f-cyclic, and bicyclic Q-decompositions of Kv.
34
Lewenczuk, Janice Gail. "Decomposition, Packings and Coverings of Complete Digraphs with a Transitive-Triple and a Pendant Arc." Digital Commons @ East Tennessee State University, 2007. https://dc.etsu.edu/etd/2053.
Full textAbstract:
In the study of design theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K3∪{e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings and coverings of the complete digraph with each of the six transitive triples with a pendant arc.
35
Santiago, Pinto Leonor. "Cobertura com restrições de conexidade." Doctoral thesis, Instituto Superior de Economia e Gestão, 2004. http://hdl.handle.net/10400.5/4705.
Full textAbstract:
Doutoramento em Matemática Aplicada à Economia e GestãoDado um grafo bipartido com classes de bipartição V e U, uma cobertura é um subconjunto C Ç V em que cada vértice de U é adjacente a pelo menos um vértice de C. 0 problema da cobertura procura uma cobertura de cardinalidade mínima. No contexto da selecção de reservas para a con¬servação de espécies, V é o conjunto de povoamentos passíveis de serem seleccionados para integrar a reserva, U o conjunto de espécies a proteger e as arestas descrevem as ocorrências das espécies nos povoamentos. Algumas coberturas apresentam, no entanto, configurações espaciais que não são ade¬quadas do ponto de vista conservacionista. Por razões de sustentabilidade a fragmentação é considerada um atributo indesejável. Assim, a conexidade tem um papel importante na protecção da biodiversidade e vários autores têm recentemente proposto algoritmos que incorporam a conexidade. Nesta dissertação considera-se a introdução explícita da conexidade no problema da cobertura, de forma a dar resposta a questões relevantes em biologia da conservação.
Given a bipartite graph with bipartition V and U, a cover is a subset C C V such that each node of U is adjacent to at least one node in C. The set cov¬ering problem seeks a minimum cardinality cover. In the context of reserve selection for conservation of species, V is a set of candidate sites from a re¬serve network, U is the set of species to be protected, and the edges describe which species are represented in each site. Some covers however may assume spatial configurations which are not adequate for conservational purposes. For sustainability reasons the fragmentation of existing natural habitats should be avoided. Thus, connectivity appears to be an important issue for persistence of biodiversity, and several authors have recently proposed algorithms which incorporate connectivity. We address the issue of explic¬itly introducing connectivity in the set covering problem, with relevance for conservation biology.
36
Francetic, Nevena. "Covering Arrays with Row Limit." Thesis, 2012. http://hdl.handle.net/1807/34006.
Full textAbstract:
Covering arrays with row limit, CARLs, are a new family of combinatorial objects
which we introduce as a generalization of group divisible designs and covering arrays. In the same manner as their predecessors, CARLs have a natural application as combinatorial models for interaction test suites. A CARL(N;t,k,v:w), is an N×k array with some empty cells. A component, which is represented by a column, takes values from a v-set called the alphabet. In each row, there are exactly w non-empty cells, that is the corresponding components have an assigned value from the alphabet. The parameter w is called the row limit. Moreover, any N×t subarray contains every of v^t distinct t-tuples of alphabet symbols at least once.
This thesis is concerned with the bounds on the size and with the construction of
CARLs when the row limit w(k) is a positive integer valued function of the number
of columns, k. Here we give a lower bound, and probabilistic and algorithmic upper
bounds for any CARL. Further, we find improvements on the upper bounds when
w(k)ln(w(k)) = o(k) and when w(k) is a constant function. We also determine the
asymptotic size of CARLs when w(k) = Θ(k) and when w(k) is constant.
Next, we study constructions of CARLs. We provide two combinatorial constructions
of CARLs, which we apply to construct families of CARLs with w(k)=ck, where c<1.
Also, we construct optimal CARLs when t=2 and w=4, and prove that there exists a
constant δ, such that for any v and k≥4, an optimal CARL(2,k,v:4) differs from the lower bound by at most δ rows, with some possible exceptions.
Finally, we define a packing array with row limit, PARL(N;t,k,v:w), in the same
way as a CARL(N;t,k,v:w) with the difference that any t-tuple is contained at most
once in any N×t subarray. We find that when w(k) is a constant function, the results on
the asymptotic size of CARLs imply the results on the asymptotic size of PARLs. Also, when t=2, we consider a transformation of optimal CARLs with row limit w=3 to
optimal PARLs with w=3.
37
Chen, Sheng-Hua, and 陳聖華. "Covering Problems in Graphs." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/16999152570419494427.
Full textAbstract:
博士國立臺灣大學
數學研究所
102
Covering problems in graphs are optimization problems about covering the vertex set V(G) or the edge set E(G) of a graph G under some additional restrictions. In other words, a emph{graph covering} of G is a collection of vertex/edge subsets of G such that each vertex/edge of G is belonged to at least one subset in this collection. Graph covering enjoys many practical applications as well as theoretical challenges. It is heavily used in various fields such as biochemistry (genomics), electrical engineering (communication networks and coding theory), computer science (algorithms and computation) and operations research (scheduling) etc. In this thesis, we consider six covering problems in graphs, which study the optimality of the following related functions. A it strong edge-coloring is a function that assigns to each edge a color such that any two edges within distance two apart receive different colors. An edge Roman dominating function is the edge version of a Roman dominating function, that is, a function f: E(G)->{0,1,2} such that every edge e with f(e)=0 is adjacent to some edge e'' with f(e'')=2. More generally, for a fixed positive integer k, a k-power Roman dominating function is a function f:V(G)->{0,1,...,k} such that every vertex u with f(u)=0 is adjacent to some vertex v with f(v)=i
38
Hsieh, Chi-Tsung, and 謝奇璁. "Covering Graphs with Directed Paths." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/98529606536829265565.
Full textAbstract:
碩士國立交通大學
應用數學系所
97
In this thesis we study an oriented version of perfect path double cover (PPDC). An oriented perfect path double cover (OPPDC) of a graph G is a collection of oriented paths in the symmetric orientation S(G) of G such that each edge of S(G) lies in exactly one of the paths and for each vertex v ∈ V (G) there is a unique path which begins in v (and thus the same holds also for terminal vertices of the paths). First we show that if G has no components which isomorphism to K3 and G is a 3-degenerate graph, then G has an OPPDC. Next we also construct an OPPDC for complete bipartite graph Kn,n and multipartite graph Km(n) (n is odd and m ≠ 3, 5),respectively.
39
Yao, Mei-Yu, and 姚美玉. "Decompositions, Packings and Coverings of Graphs with 4-cycles (4-circuits)." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/70489867970762541779.
Full textAbstract:
碩士嶺東科技大學
資訊科技應用研究所
97
ABSTRACT In this thesis we investigate the problem of finding maximum packings and minimum coverings of complete multidigraphs with 4-circuits and that of some special multicrowns with 4-cycles. The problem of decomposing multicrowns (resp. directed multicrowns) and circulant multigraphs (resp.circulant multidigraphs) into 4-cycles (resp. 4-circuits) are also studied. We give a complete solution to the maximum packing and minimum covering problem, and obtain some sufficient conditions on the existence of 4-cycle (resp. 4-circuit) decompositions of multicrowns (resp. directed multicrowns) and circulant multigraphs (resp. circulant multidigraphs)
40
Datta, Krupa R. "Generalization of Hitting, Covering and Packing Problems on Intervals." Thesis, 2017. http://etd.iisc.ernet.in/2005/3628.
Full textAbstract:
Interval graphs are well studied structures. Intervals can represent resources like jobs to be sched-uled. Finding maximum independent set in interval graphs would correspond to scheduling maximum number of non-conflicting jobs on the computer. Most optimization problems on interval graphs like independent set, vertex cover, dominating set, maximum clique, etc can be solved efficiently using combinatorial algorithms in polynomial time. Hitting, Covering and Packing problems have been ex-tensively studied in the last few decades and have applications in diverse areas. While they are NP-hard for most settings, they are polynomial solvable for intervals. In this thesis, we consider the generaliza-tions of hitting, covering and packing problems for intervals. We model these problems as min-cost flow problems using non-trivial reduction and solve it using standard flow algorithms.
Demand-hitting problem which is a generalization of hitting problem is defined as follows: Given N intervals, a positive integer demand for every interval, M points, a real weight for every point, select a subset of points H, such that every interval contains at least as many points in H as its demand and sum of weight of the points in H is minimized. Note that if the demand is one for all intervals, we get the standard hitting set problem. In this case, we give a dynamic programming based O(M + N) time algorithm assuming that intervals and points are sorted. A special case of the demand-hitting set is the K-hitting set problem where the demand of all the intervals is K. For the K-hitting set problem, we give a O(M2N) time flow based algorithm. For the demand-hitting problem, we make an assumption that no interval is contained in another interval. Under this assumption, we give a O(M2N) time flow based algorithm.
Demand-covering problem which is a generalization of covering problem is defined as follows: Given N intervals, a real weight for every interval, M points, a positive integer demand for every point, select a subset of intervals C, such that every point is contained in at least as many intervals in C as its demand and sum of weight of the intervals in C is minimized. Note that if the demand of points are one, we get the standard covering set problem. In this case, we give a dynamic programming based O(M + N log N) time algorithm assuming that points are sorted. A special case of the demand-covering set is the K-covering set problem where the demand of all the points is K. For the K-covering set problem, we give a O(MN2) time flow based algorithm. For the demand-covering problem, we give a O(MN2) time flow based algorithm.
K-pack points problem which is a generalization of packing problem is defined as follows: Given N intervals, an integer K, M points, a real weight for every point, select a subset of points Y , such that every interval contains at most K points from Y and sum of weight of the points in Y is maximized. Note that if K is one, we get the standard pack points problem. In this case, we give a dynamic pro-gramming based O(M + N) time algorithm assuming that points and intervals are sorted. For K-pack points problem, we give O(M2 log M) time flow based algorithm assuming that intervals and points are sorted.
41
"Decompositions, Packings, and Coverings of Complete Directed Graphs with a 3-Circuit and a Pendent Arc." East Tennessee State University, 2007. http://etd-submit.etsu.edu/etd/theses/available/etd-0713107-135325/.
Full text
42
Vacek, Jan. "Pokrývací množiny ve steganografii." Master's thesis, 2013. http://www.nusl.cz/ntk/nusl-330343.
Full textAbstract:
Steganography is a science which is interested in communication hiding. This work is focused on the most recent methods related to this topic. Mainly, it is matrix embedding, which uses coding theory, and sum and difference covering sets (SDCS). Rainbow coloring of grid graphs is used to receive even better results. This technique decrease amplitude of performed changes. It makes stegosystems less likely to be detected. Properties which describe behavior of each stegosystem are included for each technique. 1
43
Lafreniere, Benjamin J. "Packing Unit Disks." Thesis, 2008. http://hdl.handle.net/10012/3907.
Full textAbstract:
Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Richard Rado conjectured 1/4 and proved 1/4.41. In this thesis, we consider a variant of this problem where the disjointness constraint is relaxed: selected disks must be k-colourable with disks of the same colour pairwise-disjoint. Rado's problem is then the case where k = 1, and we focus our investigations on what can be proven for k > 1.
Motivated by the problem of channel-assignment for Wi-Fi wireless access points, in which the use of 3 or fewer channels is a standard practice, we show that for k = 3 we can cover at least 1/2.09 and for k = 2 we can cover at least 1/2.82. We present a randomized algorithm to select and colour a subset of n disks to achieve these bounds in O(n) expected time. To achieve the weaker bounds of 1/2.77 for k = 3 and 1/3.37 for k = 2 we present a deterministic O(n^2) time algorithm.
We also look at what bounds can be proven for arbitrary k, presenting two different methods of deriving bounds for any given k and comparing their performance. One of our methods is an extension of the method used to prove bounds for k = 2 and k = 3 above, while the other method takes a novel approach.
Rado's proof is constructive, and uses a regular lattice positioned over the given set of disks to guide disk selection. Our proofs are also constructive and extend this idea: we use a k-coloured regular lattice to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show that a required lattice positioning step used in the deterministic O(n^2) algorithm mentioned above is 3SUM-hard, providing evidence that this algorithm is optimal among algorithms employing such a lattice positioning approach. We also present evidence that a similar lattice positioning step used in the constructions for our better bounds for k = 2 and k = 3 may not have an efficient exact implementation.