Log in

Relevant bibliographies by topics / Domination problem / Dissertations / Theses

To see the other types of publications on this topic, follow the link: Domination problem.

Dissertations / Theses on the topic 'Domination problem'

Author: Grafiati

Published: 4 June 2021

Last updated: 18 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 dissertations / theses for your research on the topic 'Domination problem.'

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

Bramel, Michael H. "Patterns of cooperation, conflict, and domination in children's collaborative problem-solving." FIU Digital Commons, 1987. http://digitalcommons.fiu.edu/etd/1744.

Full text

Abstract:

This study examined the influence of age, expertise, and task difficulty on children's patterns of collaboration. Six- and eight-year-old children were individually pretested for ability to copy a Lego model and then paired with each other and asked to copy two more models. The design was a 3 (dyad skill level: novice, expert, or mixed) X 2 (age: six or eight) X 2 (task difficulty: moderate or complex) factorial. Results indicated that cooperation increased with age and expertise and decreased with task difficulty. However, expertise had a greater influence on younger than older children's int

APA, Harvard, Vancouver, ISO, and other styles

2

Beggas, Fairouz. "Decomposition and Domination of Some Graphs." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1051.

Full text

Abstract:

La théorie des graphes est considérée comme un vaste champ qui permet d'explorer différentes techniques de preuve des mathématiques discrètes. Ainsi, les différents problèmes traités dans cette théorie ont plein d'applications dans d'autres domaines scientifiques tels que l'informatique, la physique, la sociologie, la théorie des jeux, etc. Dans cette optique, nous proposons, dans cette thèse, de mettre l'accent sur trois problèmes de graphes, à savoir la multidécomposition de multigraphes, la [1, 2]-domination et le monitoring des arêtes. Ainsi, le fait d'explorer, dans ce travail de thèse, t

APA, Harvard, Vancouver, ISO, and other styles

3

Koller, Angela Erika. "The frequency assignment problem." Thesis, Brunel University, 2004. http://bura.brunel.ac.uk/handle/2438/4967.

Full text

Abstract:

This thesis examines a wide collection of frequency assignment problems. One of the largest topics in this thesis is that of L(2,1)-labellings of outerplanar graphs. The main result in this topic is the fact that there exists a polynomial time algorithm to determine the minimum L(2,1)-span for an outerplanar graph. This result generalises the analogous result for trees, solves a stated open problem and complements the fact that the problem is NP-complete for planar graphs. We furthermore give best possible bounds on the minimum L(2,1)-span and the cyclic-L(2,1)-span in outerplanar graphs, when

APA, Harvard, Vancouver, ISO, and other styles

4

Stevenson, David John. "Understanding the problem of cultural non-participation : discursive structures, articulatory practice and cultural domination." Thesis, Queen Margaret University, 2016. https://eresearch.qmu.ac.uk/handle/20.500.12289/7339.

Full text

Abstract:

This thesis employs a discursive methodology to analyse the policy problem of cultural non-participation. In so doing it seeks to answer the questions of what the problem is, why a problem exists, and what the existence of the problem does ‘in the real’ (Bacchi, 2009). The study draws on primary data generated in the form of policy texts, speeches and 42 in-depth qualitative interviews with individuals working in or for publicly funded cultural organisations in Scotland. Employing the methodological approach of problematisation (Foucault, 2003a [1981]), the study offers a close analysis of the

APA, Harvard, Vancouver, ISO, and other styles

5

Talon, Alexandre. "Intensive use of computing resources for dominations in grids and other combinatorial problems." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSEN079.

Full text

Abstract:

Nous cherchons à prouver de nouveaux résultats en théorie des graphes et combinatoire grâce à la vitesse de calcul des ordinateurs, couplée à des algorithmes astucieux. Nous traitons quatre problèmes. Le théorème des quatre couleurs affirme que toute carte d’un monde où les pays sont connexes peut être coloriée avec 4 couleurs sans que deux pays voisins aient la même couleur. Il a été le premier résultat prouvé en utilisant l'ordinateur, en 1989. Nous souhaitions automatiser encore plus cette preuve. Nous expliquons la preuve et fournissons un programme qui permet de la réétablir, ainsi que d'

APA, Harvard, Vancouver, ISO, and other styles

6

Harutyunyan, 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 text

Abstract:

A dominating set in a graph is a set S of vertices such that every vertex not in S is adjacent to a member S. A global defensive alliance in a graph is a dominating set S with the property that every vertex in S has in its closed neighborhood at least as many vertices in S as in V -- S. A global offensive alliance in a graph is a dominating set S with the property that every vertex in V -- S has in its closed neighborhood at least as many vertices in S as in V -- S.<br>We first study alliances in graphs. There are many results in this area. For example, it is known that every connected n-verte

APA, Harvard, Vancouver, ISO, and other styles

7

ALBUQUERQUE, MAYRA CARVALHO. "MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2018. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=34169@1.

Full text

Abstract:

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO<br>Esta tese faz um estudo do problema do Conjunto Dominante, um problema NP-difícil de grande relevância em aplicações relacionadas ao projeto de rede sem fio, mineração de dados, teoria de códigos, dentre outras. O conjunto dominante mínimo em um grafo é um conjunto mínimo de vértices de modo que cada vértice do grafo pertence a este conjunto ou é adjacente a um vértice que pertence a ele. Três variantes do problema foram estudadas; primeiro, uma variante na qual considera peso

APA, Harvard, Vancouver, ISO, and other styles

8

Ma, Ka Leung. "In solving the dominating set problem : group theory approach." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape10/PQDD_0005/NQ40311.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Gründlingh, Werner R. "Two new combinatorial problems involving dominating sets for lottery schemes /." Link to the online version, 2004. http://hdl.handle.net/10019.1/1388.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Grundlingh, Werner R. "Two new combinatorial problems involving dominating sets for lottery schemes." Thesis, Stellenbosch : University of Stellenbosch, 2004. http://hdl.handle.net/10019.1/1388.

Full text

Abstract:

Thesis (PhD (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2004.<br>Suppose a lottery scheme consists of randomly selecting an unordered winning n-subset from a universal set of m numbers, while a player participates in the scheme by purchasing a playing set of any number of unordered n-subsets from the same universal set prior to a winning draw, and is awarded a prize if ...

APA, Harvard, Vancouver, ISO, and other styles

11

Ullmert, Thomas [Verfasser]. "Hub Location: Finite Dominating Sets and Interdiction Problems / Thomas Ullmert." München : Verlag Dr. Hut, 2021. http://d-nb.info/123284795X/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Coelho, Rafael Santos. "The k-hop connected dominating set problem: approximation algorithms and hardness results." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-27062017-101521/.

Full text

Abstract:

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G, there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (Mink-CDS). We prove that Mink-CDS is NP-hard on planar bipartite graphs of maximum degree 4. We also prove that Mink-CDS is APX-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for Mink-CDS on bipar-

APA, Harvard, Vancouver, ISO, and other styles

13

Maliti, Dyfrig Joseph. "Autorité et pouvoir : approches historique, analytique et critique d'un problème de philosophie politique." Thesis, Strasbourg, 2012. http://www.theses.fr/2012STRAK016.

Full text

Abstract:

L’autorité étant une forme de « pouvoir » fondée sur la soumission à la hiérarchie, à l’inégalité et aux ordres sociaux préétablis, a été rejetée par les Modernes parce qu’elle est incompatible avec le principe même de la démocratie. Paradoxalement, suite à l’affaiblissement de l’autorité dans le monde moderne, on souhaite aujourd’hui son « retour ». De ce fait, notre réflexion s’est donnée pour tâche d’étudier, dans le domaine de la philosophie politique, les relations complexes qui existent entre les concepts d’autorité et de pouvoir en répondant aux questions : Qu’est-ce que l’autorité et l

APA, Harvard, Vancouver, ISO, and other styles

14

Oliveira, Rommel Teodoro de. "Sobre conjuntos dominantes eficientes em grafos." Universidade Federal de Goiás, 2009. http://repositorio.bc.ufg.br/tede/handle/tde/2901.

Full text

Abstract:

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-08-12T15:13:32Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5)<br>Made available in DSpace on 2014-08-12T15:13:32Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5) Previous issue date: 2009-03-12<br>Given a graph G = (V;E) and a set of vertices D V, a

APA, Harvard, Vancouver, ISO, and other styles

15

Defrain, Oscar. "On the dualization problem in graphs, hypergraphs, and lattices." Thesis, Université Clermont Auvergne‎ (2017-2020), 2020. http://www.theses.fr/2020CLFAC022.

Full text

Abstract:

Cette thèse porte sur la théorie des graphes, des hypergraphes, et des treillis. Nous nous intéressons à la complexité du problème de dualisation des fonctions monotones Booléennes, ainsi qu’à ses généralisations, à travers les différentes formes qu’il prend dans ces structures: énumération des dominants minimaux, des transversaux minimaux, dualisation dans les treillis, et énumération des éléments meet-irréductibles. De nouveaux résultats positifs et négatifs sont obtenus, et des directions de recherche futures sont proposées. La thèse se découpe comme suit. Dans une première partie, nous nou

APA, Harvard, Vancouver, ISO, and other styles

16

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 text

Abstract:

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 (stro

APA, Harvard, Vancouver, ISO, and other styles

17

Ho, Yiu Yu. "Global secure sets of trees and grid-like graphs." Doctoral diss., University of Central Florida, 2011. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/4922.

Full text

Abstract:

However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in (BDH07) for exactly this purpose. The non-empty set S is a secure set if every subset Xsubset of]S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In (BDH07), the authors presented an interesting c

APA, Harvard, Vancouver, ISO, and other styles

18

Neggazi, Brahim. "Self-stabilizing algorithms for graph parameters." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10041/document.

Full text

Abstract:

Le concept d'auto-stabilisation a été introduit par Dijkstra en 1973. Un système distribué est auto-stabilisant s'il peut démarrer de n'importe quelle configuration initiale et retrouver une configuration légitime en un temps fini par lui-même et sans aucune intervention extérieure. La convergence est également garantie lorsque le système est affecté par des fautes transitoires, ce qui en fait une approche élégante, non masquante, pour la tolérance aux pannes. L'auto-stabilisation a été étudiée dans divers domaines des systèmes distribués tels que les problèmes de synchronisation de l'horloge,

APA, Harvard, Vancouver, ISO, and other styles

19

Le, Bodic Pierre. "Variantes non standards de problèmes d'optimisation combinatoire." Thesis, Paris 11, 2012. http://www.theses.fr/2012PA112190.

Full text

Abstract:

Cette thèse est composée de deux parties, chacune portant sur un sous-domaine de l'optimisation combinatoire a priori distant de l'autre. Le premier thème de recherche abordé est la programmation biniveau stochastique. Se cachent derrière ce terme deux sujets de recherche relativement peu étudiés conjointement, à savoir d'un côté la programmation stochastique, et de l'autre la programmation biniveau. La programmation mathématique (PM) regroupe un ensemble de méthodes de modélisation et de résolution, pouvant être utilisées pour traiter des problèmes pratiques que se posent des décideurs. La pr

APA, Harvard, Vancouver, ISO, and other styles

20

Kao, Mong-Jen, and 高孟駿. "Capacitated Domination Problem." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/73743858229094012405.

Full text

Abstract:

碩士<br>國立臺灣大學<br>資訊工程學研究所<br>96<br>We consider a generalization of the well-known domination problem on graphs. The soft capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demand of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies that the demand of each vertex in V is met by the capacities of verti

APA, Harvard, Vancouver, ISO, and other styles

21

Burger, Alewyn Petrus. "The queen's domination problem." Thesis, 1998. http://hdl.handle.net/10500/16179.

Full text

Abstract:

The queens graph Qn has the squares of then x n chessboard as its vertices; two squares are adjacent if they are in the same row, column or diagonal. A set D of squares of Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a square in D. If no two squares of a set I are adjacent then I is an independent set. Let 'J'(Qn) denote the minimum size of a dominating set of Qn and let i(Qn) denote the minimum size of an independent dominating set of Qn. The main purpose of this thesis is to determine new values for'!'( Qn). We begin by discussing the most important

APA, Harvard, Vancouver, ISO, and other styles

22

Lu, Shao-chia, and 呂紹甲. "A Survey on Broadcast Domination Problem." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/44982216878959260504.

Full text

Abstract:

碩士<br>國立清華大學<br>資訊工程學系<br>97<br>A broadcast domination function on a graph $G=(V,E)$ is a function $f$ that maps $V$ into $\{0,1,\dots,k\}$ such that every vertex of $G$ within distance $f(v)$ from some vertex $v$ with $f(v)>0$. The cost of a broadcast domination function $f$ is $\Sigma_{v\in V}f(v)$. The broadcast domination problem on $G$ is to find a minimum cost broadcast domination function on $G$. In this thesis, we present an overview of the broadcast domination problem and some results on characterizations of radial trees.

APA, Harvard, Vancouver, ISO, and other styles

23

Huang, Abner Chih Yi, and 黃智沂. "K-Tuple Domination Problem on Graphs." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/73931871506796987962.

Full text

Abstract:

碩士<br>國立清華大學<br>資訊工程學系<br>95<br>In a graph $G(V,E)$, a vertex $v$ dominates a vertex $u$ if $u=v$ or there is an edge from $v$ to $u$. A dominating set of $G$ is a subset $D$ of $V$ such that every vertex in $V$ is dominated by at least one vertex in $D$. Domination problem, that is proposed by K{\"o}nig, and its variations have fruitful literature more than $300$ publications. One class of those interesting variations is the {\it multiple domination problems}, i.e., each vertex in $V$ requires to be dominated by more than one vertex in $D$. In this thesis, we study the $k$-tuple domination pr

APA, Harvard, Vancouver, ISO, and other styles

24

Yeh, Ting-Hsi, and 葉庭熙. "Roman Domination Problem on Permutation Graphs." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/73395271866567531796.

Full text

Abstract:

碩士<br>國立清華大學<br>資訊工程學系<br>95<br>A roman domination problem is quite a hot variant domination problem in recent years. In one graph G = (V, E), a roman domination function is a function f : V �� {0, 1, 2}, that each one vertex u with f(u) = 0 is adjacent to at least one vertex v with f(v) = 2, among them u and v belongs to V. The weight of a roman domination function f is the sum of the weight of V. A roman domination number of a graphs G is the smallest weight of the possible roman domination function f. When give one permutation graph, we can provide a polynomial algorithm (O(n5))to find out

APA, Harvard, Vancouver, ISO, and other styles

25

Chen, Han-Lin, and 陳翰霖. "Approximation Algorithms for Capacitated Domination Problem." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/22158579659765670266.

Full text

Abstract:

碩士<br>臺灣大學<br>資訊工程學研究所<br>98<br>We consider the Capacitated Domination problem, which models a service requirement assignment scenario and is also a generalization of the well known Dominating Set problem. In this problem, given a graph with three parameters defined on each vertex, namely cost, capacity, and demand, we want to find an assignment of demands to vertices of least cost such that the demand of each vertex is satisfied subject to the capacity constraint of each vertex providing the service. In terms of polynomial time approximations, we present logarithmic approximation algorithm

APA, Harvard, Vancouver, ISO, and other styles

26

Liu, Chia Yun, and 劉佳芸. "The Double Domination Problem in Graphs." Thesis, 1995. http://ndltd.ncl.edu.tw/handle/38491765947245808874.

Full text

Abstract:

碩士<br>國立交通大學<br>應用數學研究所<br>83<br>Each vertex of a graph G=(V,E) is said to dominate itself and all vertices adjacent to it. A set D .lhkeq. V is a double dominating set of G if each vertex of V is dominated by at least two vertices in D. The double domination problem is to find the smallest size of a double dominating set of a given graph G, which is called the double domination number dd(G). In this paper, we first prove that the double domination problem is NP-complete for general graphs,

APA, Harvard, Vancouver, ISO, and other styles

27

Bird, William Herbert. "Computational methods for domination problems." Thesis, 2017. https://dspace.library.uvic.ca//handle/1828/8634.

Full text

Abstract:

For a graph G, the minimum dominating set problem is to find a minimum size set S of vertices of G such that every vertex is either in S or adjacent to a vertex in the set. The decision version of this problem, which asks whether G has a dominating set of a particular size k, is known to be NP-complete, and no polynomial time algorithm to solve the problem is currently known to exist. The queen domination problem is to find the minimum number of queens which, collectively, can attack every square on an n by n chess board. The related border queen problem is to find such a collection of queens

APA, Harvard, Vancouver, ISO, and other styles

28

LIN, YI-CHUN, and 林宜駿. "Outer-paired Domination Problem in Block Graphs." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/94167567502148181857.

Full text

Abstract:

碩士<br>國立臺灣科技大學<br>資訊管理系<br>104<br>Let G = (V, E) be an undirected graph, where V(G) and E(G) are vertex and edge sets of G, respectively. For simplicity, we also use V and E to represent V(G) and E(G),respectively, when the context is clear. A set D is a dominating set of a graph G if every vertex in V \ D is adjacent to at least one vertex in D. The domination problem and its variants were extensively studied, e.g., independent domination, rainbow domination, total domination, roman domination, etc. We can ﬁnd that all variants on the domination problem are adding some constraints on the domi

APA, Harvard, Vancouver, ISO, and other styles

29

Chang, Yung-Li, and 張永立. "Efficient Minus Domination Problem on Block Graphs." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/51308210507211991009.

Full text

Abstract:

碩士<br>國立中正大學<br>資訊工程研究所<br>91<br>A three-valued function $f$ defined on the vertices of a graph $G = (V, E)$, $f : V \rightarrow \{-1, 0, 1\}$, is an efficient minus dominating function if the sum of its function values over any closed neighborhood equals to one. That is, for every $v \in V$, $\sum_{u \in N[v]}f(u) = 1$, where $N[v]$ consists of $v$ and all vertices adjacent to $v$. The sum of the function values of all vertices is called the weight of $f$. The efficient minus domination problem is to find the efficie

APA, Harvard, Vancouver, ISO, and other styles

30

WANG, MIN-ZHONG, and 王銘忠. "The K-domination problem of a graph." Thesis, 1986. http://ndltd.ncl.edu.tw/handle/20335692303013507015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Lin, Yu-Cheng, and 林禹丞. "The Outer-paired Domination Problem on Proper Interval Graphs." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/u853ty.

Full text

Abstract:

碩士<br>國立臺灣科技大學<br>資訊管理系<br>105<br>Let G=(V,E) be an undirected graph, where V(G) and E(G) are vertex and edge sets of G, respectively. For simplicity, we also use V and E to represent V(G) and E(G), respectively. For any vertex vV , the open neighborhood of v is the set NG(v) = {uV : uv E}. The closed neighborhood of v is NG[v] = NG(v){v}. For simplicity, NG(v) and NG[v] are simply written as N(v) and N[v], respectively. A set D is a dominating set of a graph G if every vertex in V\D is adjacent to at least one vertex in D. The domination problem and its variants were extensively studied,

APA, Harvard, Vancouver, ISO, and other styles

32

Yang, Si-Han, and 楊斯涵. "The 2-tuple total domination problem on Harary graphs." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/654xmj.

Full text

Abstract:

碩士<br>國立臺北商業大學<br>資訊與決策科學研究所<br>105<br>Let G be a graph with minimum degree at least 2. A vertex subset is a 2-tuple total dominating set of G if every vertex is adjacent to at least two vertices in S. The 2-tuple total domination number of G is the minimum size of a 2-tuple total dominating set. In this thesis, we are concerned with the 2-tuple total domination number of a Harary graph H_{2m+1, 2n+1} with 2n+1=(2m+1)\ell. For m = 1 and m = 2, we show that the numbers are 2\ell and 2\ell+1, respectively.

APA, Harvard, Vancouver, ISO, and other styles

33

Lin, Chin-Fu, and 林勁甫. "A Study of Disjunctive Total Domination Problem on Trees." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/83552645429406426721.

Full text

Abstract:

碩士<br>國立東華大學<br>資訊工程學系<br>104<br>For a graph G = (V; E), D ⊆ V is a dominating set if every vertex in V \ D has a neighbor in D. If every vertex in V has to be adjacent to a vertex of D, then D is called a total dominating set of G. The (total) domination problem on G is to nd a (total) dominating set D of the minimum cardinality. The (total) domination problem is wellstudied. Recently, the following variant is proposed. A vertex subset D is a disjunctive total dominating set of G if every vertex of V is adjacent to a vertex of D or has at least two vertices in D at distance 2 from it. The di

APA, Harvard, Vancouver, ISO, and other styles

34

Chen, Ya-Mei, and 陳雅玫. "The Fault Tolerant Domination Problem on Strongly Chordal Graphs." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/89509799514631971665.

Full text

Abstract:

碩士<br>國立中正大學<br>資訊工程研究所<br>89<br>Given a graph G = (V, E) and a fault tolerant function f from V to N, a dominating set D(subset of V) is fault tolerant if | D∩N[v] | >= f(v) for all v in V. Given a graph G = (V, E) and a function g,from V to integers, the weight of g is defined as w(g) =Σ(v in V) g(v). For a vertex v in V, let g[v] =Σ(u in N[v]) g(u). A signed dominating function of G is a function g,from V to {-1,1}, such that g[v] >= 1 for all v in V. The signed domination number rs(G)(gamma_s(G)) of G is the minimum weight of a signed dominating function on G. We call a signed d

APA, Harvard, Vancouver, ISO, and other styles

35

Fata, Elaheh. "On Two Combinatorial Optimization Problems in Graphs: Grid Domination and Robustness." Thesis, 2013. http://hdl.handle.net/10012/7806.

Full text

Abstract:

In this thesis, we study two problems in combinatorial optimization, the dominating set problem and the robustness problem. In the first half of the thesis, we focus on the dominating set problem in grid graphs and present a distributed algorithm for finding near optimal dominating sets on grids. The dominating set problem is a well-studied mathematical problem in which the goal is to find a minimum size subset of vertices of a graph such that all vertices that are not in that set have a neighbor inside that set. We first provide a simpler proof for an existing centralized algorithm that const

APA, Harvard, Vancouver, ISO, and other styles

36

Wu, Chia-Wen, and 吳嘉雯. "A Study on the Double Total Domination Problem in Harary Graphs." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/7w9286.

Full text

Abstract:

碩士<br>國立臺北商業大學<br>資訊與決策科學研究所<br>107<br>Let G = (V, E) be a graph with minimum degree at least 2. A vertex subset D is a double total dominating set of G if every vertex of G is adjacent to at least two vertices in D. The double total domination number of G, denoted as γ×2,t(G), is the size of a minimum double total dominating set in G. In this thesis, we are concerned with the double total domination number of the Harary graph H_(2m+1,2n), where 2m + 1 is the degree of each vertex and 2n is the number of vertices. Let 2n = (2m+1)l+r, where 0 <= r <= 2m. When r = 0 or m + 1 <= r <= 2m, γ×2,

APA, Harvard, Vancouver, ISO, and other styles

37

Xu, Shuo-Hong, and 徐碩鴻. "An Algorithm for Solving the Power Domination Problem on Honeycomb Meshes." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/22363001906058279316.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Yang, Hong-Ding, and 楊弘鼎. "A Study of Disjunctive Total domination Problem on Tori and Grid Graphs." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/jm4gu6.

Full text

Abstract:

碩士<br>國立東華大學<br>資訊工程學系<br>105<br>For a graph G = (V;E), a subset D of V is a total dominating set of G if every vertex in V has to be adjacent to a vertex of D. Vertex subset D is a disjunctive total dominating set if every vertex of V is adjacent to a vertex of D or has at least two vertices in D at distance 2 from it. The disjunctive total domination problem on G is to find a disjunctive total dominating set D of the minimum cardinality. The cardinality of a minimum disjunctive total dominating set of G is called the disjunctive total domination number of G. In this thesis, we study the disj

APA, Harvard, Vancouver, ISO, and other styles

39

Tsai, Yuan-Hsiang, and 蔡元翔. "A Linear-Time Algorithm for Roman Domination Problem on Bounded Treewidth Graphs." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/7hcap9.

Full text

Abstract:

碩士<br>國立東華大學<br>資訊工程學系<br>95<br>A Roman dominating function on a graph G = (V, E) is a function f : V → f(0, 1, 2) satisfying that every vertex u with f(u) = 0 has a neighbor v with f(v) = 2. The weight of the Roman dominating function f is the sum of f(v) for the vertices belonging to V. The Roman domination number of a graph G is the minimum weight of all possible Roman dominating functions on G. The motivation of Roman domination is in assigning the minimum armies to protect all castles and villages at the age of Roman Empire. If two armies locate in an area, they can protect the area that

APA, Harvard, Vancouver, ISO, and other styles

40

Liao, Chi-Hyi, and 廖之翊. "A Linear-Time Algorithm for the Maximum Restricted Paired-Domination Problem in Cographs." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/17244781782059681668.

Full text

Abstract:

碩士<br>朝陽科技大學<br>資訊工程系碩士班<br>97<br>Let G = (V;E) be a graph without isolated vertices. A set S ⊆ V is a paired-dominating set if every vertex in V − S is adjacent to a vertex in S and the subgraph G[S] induced by S contains a perfect matching M. The paired-domination problem is to find a paired-dominating set of G with minimum cardinality. Let R be a subset of vertices ofG, PDbe any paired-dominating set of G, and let M be a perfect matching M of G[PD]. If e = (u, v) ∈ M, we say that u and v form a pair in M. A pair in a matching M is called free-pair if neither of its both vertices is inR. A m

APA, Harvard, Vancouver, ISO, and other styles

41

Lu, Chin Lung, and 盧錦隆. "Efficient Algorithms for the Weighted k-Domination Problem and its Variants on Interval and Circular-arc Graphs." Thesis, 1993. http://ndltd.ncl.edu.tw/handle/71172055066030475228.

Full text

Abstract:

碩士<br>國立中正大學<br>資訊工程研究所<br>81<br>Let G=(V,E) be a simple graph, m be the number of edges and n be the number of vertices. The length of a path is the number of edges in the path. The distance d(x,y) from vertex x to vertex y in G is the minimum length of a path from x to y. If d( x,y) is less than or equal to k, then we say that x dominates y within distance k (or say that x k-dominate y), and vice versa. A subset D of V is called a k-dominating set of G if for every vertex x in V, there ex

APA, Harvard, Vancouver, ISO, and other styles

42

Suchý, Ondřej. "Parametrizovaná složitost." Doctoral thesis, 2011. http://www.nusl.cz/ntk/nusl-300399.

Full text

Abstract:

Title: Parameterized Complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisor's e-mail address: honza@kam.mff.cuni.cz Abstract: This thesis deals with the parameterized complexity of NP-hard graph problems. We explore the complexity of the problems in various scenarios, with respect to miscellaneous parameters and their combina- tions. Our aim is rather to classify in this multivariate manner whether the particular parameters make the problem fixed-parameter tractable or intractable than to present the algorithm achieving t

APA, Harvard, Vancouver, ISO, and other styles

43

Chang, Chan-Wei, and 張展維. "The F-domination Problems on Graphs." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/11149351031061996851.

Full text

Abstract:

博士<br>國立東華大學<br>應用數學系<br>99<br>Given a graph G and a set S⊆V(G), a vertex v is said to be F-dominated by a vertex w in S if either v=w, or v∉S and there exists a vertex u in V(G)-S such that P:wuv is a path in G. A set S⊆V(G) is an F-dominating set of G if every vertex v is F-dominated by a vertex w in S. The F-domination number of G, denoted by γ_{F}(G), is the minimum cardinality of an F-dominating set of G. We consider the F-domination problem of graphs in this thesis. We prove that the F-domination problem is an NP-complete problem and give formulas to compute the F-domination number of P_

APA, Harvard, Vancouver, ISO, and other styles

44

Wang, Fu-Hsing, and 王福星. "Domination Related Problems on Some Interconnection Networks." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/91310579141360223698.

Full text

Abstract:

博士<br>國立臺灣科技大學<br>資訊管理系<br>92<br>Graph theorists have much been attracted by the researches on domination related problems for their strongly practical applications and theoretical interesting. This dissertation presents results of some domination problems on interconnection networks and is divided into three parts. The first part focuses on the characterizations of star graphs and finds the perfect dominating sets and total dominating sets for star graphs. These results are helpful to derive an upper bound to the size of the minimum feedback vertex set for star graphs. Also, by applying the p

APA, Harvard, Vancouver, ISO, and other styles

45

Lin, Shaw-Waei, and 林劭韡. "Maximum-Weight Minimal Domination Problems on Interval Graphs." Thesis, 1989. http://ndltd.ncl.edu.tw/handle/86490147474119258471.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Yu, Zheng-Wu, and 俞征武. "On some domination problems in the planar points." Thesis, 1989. http://ndltd.ncl.edu.tw/handle/36866444553421938624.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Liao, Chung-Shou, and 廖崇碩. "Graph-Theoretic Domination and Related Problems with Applications." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/36465103387692829378.

Full text

Abstract:

博士<br>國立臺灣大學<br>資訊工程學研究所<br>97<br>Within the last thirty years, concurrent with the growth of such areas as computer science, electrical and computer engineering, and operations research, graph theory has seen explosive growth and perhaps the fastest-growing area within graph theory is the study of domination and related problems. In particular, there has appeared a significant portion of literature from an algorithmic point of view. The concept of domination in graph theory is a natural model for many location problems in operations research. According to different requirements for practical

APA, Harvard, Vancouver, ISO, and other styles

48

Liu, Chih-Shan, and 劉至善. "A Study of Domination Problems on Probe Interval Graphs." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/93813818032334150295.

Full text

Abstract:

碩士<br>國立東華大學<br>資訊工程學系<br>94<br>Let G = (V; E) be a graph. A vertex setW µ V is a dominating set of G if every vertex of V is either in W or adjacent to a vertex in W. A dominating set W is independent if there is no edge between any two vertices of W. The (independent) domination problem of G is to ‾nd a (independent) dominating set W with minimum cardinality. A graph G is an interval graph if there is a collection of intervals on the real line and a 1-1 mapping from the vertices of G to these intervals, such that two vertices are adjacent if and only if their corresponding intervals intersec

APA, Harvard, Vancouver, ISO, and other styles

49

Lin, Jin Yong, and 林晉永. "Algorithms and Hardness for Signed and Minus Domination Problems." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/47298793310654873664.

Full text

Abstract:

碩士<br>國立清華大學<br>資訊工程學系<br>103<br>A {\em domination problem} in graph theorem is that in given graph, we choose some vertices or edges, or assign values to vertices such that the graph can accord with the rule of the problem. In this paper, we study the algorithms and hardness for {\em Signed domination (SD) problem} and {\em Minus domination (MD) problem}. The singed domination problem is that we assign value $\{-1,+1\}$ to all vertices, the minus domination problem is that we assign value $\{-1,0,+1\}$ to all vertices, both of two problems ask that for all vertices, the sum value of the verte

APA, Harvard, Vancouver, ISO, and other styles

50

Ma, Ka Leung. "Partition algorithm for the dominating set problem." Thesis, 1990. http://spectrum.library.concordia.ca/3870/1/MM59150.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!