To see the other types of publications on this topic, follow the link: Maximum Independent Set problem.
Dissertations / Theses on the topic 'Maximum Independent Set problem'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 30 dissertations / theses for your research on the topic 'Maximum Independent Set 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
Lê, Ngoc C. "Algorithms for the Maximum Independent Set Problem." Doctoral thesis, Technische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola", 2015. http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-172639.
Full textAbstract:
This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs.
We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in:
+ some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs);
+ some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs);
+ some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs.
Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes.
We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem.
We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs.
We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered.
Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.
2
Cenek, Eowyn W. "Subtree overlap graphs and the maximum independent set problem." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ28923.pdf.
Full text
3
Butenko, Sergiy. "Maximum independent set and related problems, with applications." [Gainesville, Fla.] : University of Florida, 2003. http://purl.fcla.edu/fcla/etd/UFE0001011.
Full text
4
Dabrowski, Konrad K. "Structural solutions to maximum independent set and related problems." Thesis, University of Warwick, 2012. http://wrap.warwick.ac.uk/54515/.
Full textAbstract:
In this thesis, we study some fundamental problems in algorithmic graph theory. Most natural problems in this area are hard from a computational point of view. However, many applications demand that we do solve such problems, even if they are intractable. There are a number of methods in which we can try to do this: 1) We may use an approximation algorithm if we do not necessarily require the best possible solution to a problem. 2) Heuristics can be applied and work well enough to be useful for many applications. 3) We can construct randomised algorithms for which the probability of failure is very small. 4) We may parameterize the problem in some way which limits its complexity. In other cases, we may also have some information about the structure of the instances of the problem we are trying to solve. If we are lucky, we may and that we can exploit this extra structure to find efficient ways to solve our problem. The question which arises is - How far must we restrict the structure of our graph to be able to solve our problem efficiently? In this thesis we study a number of problems, such as Maximum Indepen- dent Set, Maximum Induced Matching, Stable-II, Efficient Edge Domina- tion, Vertex Colouring and Dynamic Edge-Choosability. We try to solve problems on various hereditary classes of graphs and analyse the complexity of the resulting problem, both from a classical and parameterized point of view.
5
Huang, Fuzhuo. "On the maximum weighted independent set problem with applications in wireless sensor networks." Thesis, Boston University, 2013. https://hdl.handle.net/2144/12785.
Full textAbstract:
Thesis (Ph.D.)--Boston University
PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.The Maximum Weighted Independent Set (MWIS) Problem considers a graph with weights assigned to the nodes and seeks to discover the "heaviest" independent set, that is, a set of nodes with maximal total weight so that no two nodes in the set are connected by an edge. The MWIS problem arises in many application domains including maximum a posteriori estimation, error-correcting coding, spatial statistics, and communication networks. It has been shown to be combinatorially hard (NP-complete) and there has been extensive work in the literature proposing a variety of heuristics. In this dissertation, we propose a novel, low-complexity and distributed algorithm that yields high-quality feasible solutions to this problem. Our proposed algorithm consists of two phases, each of which requires only local information and is based on message-passing between neighboring nodes. The first phase solves Linear Programming (LP) relaxations of the MWIS problem. We consider two LP relaxations: one involving simple edge constraints and another which is tighter and accounts for all cliques of the graph. The second phase of our algorithm uses the solution of the relaxation and constructs a feasible solution to the MWIS problem. We establish that we always obtain a feasible solution to MWIS and that for special cases of graphs the solution is optimal. More specifically, with the clique-based relaxation we can guarantee an optimal solution for the large class of so called perfect graphs. When using the edge-based relaxation, our algorithm guarantees optimality for bipartite graphs and obtains with high probability near-optimal solutions for general graphs with large weights. We also establish that our algorithms can run in an asynchronous fashion and provide the same optimality guarantees as the synchronous version. We apply our algorithms to two different applications in wireless sensor networks. The first application concerns the problem of efficiently "emptying" a wireless sensor network that has accumulated a large amount of data at its nodes and seeks to relay them to designated gateways so as to maximize a concave function of achievable transmission rates. The other application is the problem of scheduling wireless networks with stochastic packet arrivals on the links and constant transmission rates. In both cases we show that our algorithms lead to significant performance gains over the current state-of-the art.
6
Warrier, Deepak. "A branch, price, and cut approach to solving the maximum weighted independent set problem." Texas A&M University, 2003. http://hdl.handle.net/1969.1/5814.
Full textAbstract:
The maximum weight-independent set problem (MWISP) is one of the most
well-known and well-studied NP-hard problems in the field of combinatorial
optimization.
In the first part of the dissertation, I explore efficient branch-and-price (B&P)
approaches to solve MWISP exactly. B&P is a useful integer-programming tool for
solving NP-hard optimization problems. Specifically, I look at vertex- and edge-disjoint
decompositions of the underlying graph. MWISPâÂÂs on the resulting subgraphs are less
challenging, on average, to solve. I use the B&P framework to solve MWISP on the
original graph G using these specially constructed subproblems to generate columns. I
demonstrate that vertex-disjoint partitioning scheme gives an effective approach for
relatively sparse graphs. I also show that the edge-disjoint approach is less effective than
the vertex-disjoint scheme because the associated DWD reformulation of the latter
entails a slow rate of convergence.
In the second part of the dissertation, I address convergence properties associated
with Dantzig-Wolfe Decomposition (DWD). I discuss prevalent methods for improving the rate of convergence of DWD. I also implement specific methods in application to the
edge-disjoint B&P scheme and show that these methods improve the rate of
convergence.
In the third part of the dissertation, I focus on identifying new cut-generation
methods within the B&P framework. Such methods have not been explored in the
literature. I present two new methodologies for generating generic cutting planes within
the B&P framework. These techniques are not limited to MWISP and can be used in
general applications of B&P. The first methodology generates cuts by identifying faces
(facets) of subproblem polytopes and lifting associated inequalities; the second
methodology computes Lift-and-Project (L&P) cuts within B&P. I successfully
demonstrate the feasibility of both approaches and present preliminary computational
tests of each.
7
Sachdeva, Sandeep. "Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem." Thesis, Texas A&M University, 2004. http://hdl.handle.net/1969.1/3251.
Full textAbstract:
We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.
8
Lê, Ngoc C. [Verfasser], Ingo [Akademischer Betreuer] Schiermeyer, Ingo [Gutachter] Schiermeyer, and Jochen [Gutachter] Harant. "Algorithms for the Maximum Independent Set Problem / Ngoc C. Lê ; Gutachter: Ingo Schiermeyer, Jochen Harant ; Betreuer: Ingo Schiermeyer." Freiberg : Technische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola", 2015. http://d-nb.info/1220837970/34.
Full text
9
Morel, Gregory. "Stabilité et coloration des graphes sans P5." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENM042/document.
Full textAbstract:
La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des graphes. Il s'agit en effet de la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle on ignore encore s'il existe un algorithme polynomial permettant de résoudre le problème du stable maximum. Or ce problème, dont on sait qu'il est difficile en général, est d'une grande importance en pratique (problèmes de planification, d'allocation de registres dans un processeur, biologie moléculaire...). Dans cette thèse, nous commençons par dresser un état de l'art complet des méthodes utilisées pour résoudre le problème dans des sous-classes de graphes sans P5, puis nous étudions et résolvons ce problème dans une sous-classe particulière, la classe des graphes sans P5 3-colorables. Nous apportons également des solutions aux problèmes de la reconnaissance et de la coloration de ces graphes, chaque fois en temps linéaire. Enfin, nous définissons, caractérisons et sommes capables de reconnaître les graphes "chain-probe", qui sont les graphes auxquels il est possible de rajouter des arêtes entre certains sommets de sorte qu'ils soient bipartis et sans P5. Les problèmes de ce type proviennent de la génétique et ont également des applications en intelligence artificielleThe class of P5-free graphs, namely the graphs without induced chains with five vertices, is of particular interest in graph theory. Indeed, it is the smallest class defined by only one forbidden connected induced subgraph for which the complexity of the Maximum Independent Set problem is unknown. This problem has many applications in planning, CPU register allocation, molecular biology... In this thesis, we first give a complete state of art of the methods used to solve the problem in P5-free graphs subclasses; then we study and solve this problem in a particular subclass, the class of 3-colorable P5-free graphs. We also bring solutions to recognition and coloring problems of these graphs, each time in linear time. Finally, we define, characterize, and are able to recognize "chain-probe" graphs, namely the graphs for which we can add edges between particular vertices such that the resulting graph is bipartite and P5-free. Problems of this type come from genetics and have application in I.A
10
Laboratory, Hirata, Tomio Hirata, Takao Ono, and Xuzhen Xie. "Approximation Algorithms for Weighted Independent Set Problem." INTELLIGENT MEDIA INTEGRATION NAGOYA UNIVERSITY / COE, 2005. http://hdl.handle.net/2237/10363.
Full text
11
Bristow, Andrew IV. "The INDEPENDENT SET Decision Problem is NP-complete." VCU Scholars Compass, 2011. http://scholarscompass.vcu.edu/etd/2573.
Full textAbstract:
In the 1970's computer scientists developed the theory of computational complexity. Some problems seemed hard-to-compute, while others were easy. It turned out that many of the hard problems were equally hard in a way that could be precisely specified. They became known as the NP-complete problems. The SATISFIABILITY problem (SAT) was the first problem to be proved NP-complete in 1971. Since then numerous other hard-to-solve problems have been proved to be in NP-complete. In this paper we will examine the problem of how to find a maximum independent set of vertices for a graph. This problem is known as Maximum Independent Set (MIS) for a graph. The corresponding decision problem for MIS is the question, given an integer K, is there a independent set with at least K vertices? This decision problem is INDEPENDENT SET (IS). The intention of this paper is to show through polynomial transformation that IS is in the set of NP-complete Problems. We intend to show that 3SAT is NP-complete and then using this fact, that IS is NP-complete.
12
Bashar, Mohammad Ehsanul. "Average case analysis of algorithms for the maximum subarray problem." Thesis, University of Canterbury. Computer Science and Software Engineering, 2007. http://hdl.handle.net/10092/1194.
Full textAbstract:
Maximum Subarray Problem (MSP) is to find the consecutive array portion that maximizes the sum of array elements in it. The goal is to locate the most useful and informative array segment that associates two parameters involved in data in a 2D array. It's an efficient data mining method which gives us an accurate pattern or trend of data with respect to some associated parameters. Distance Matrix Multiplication (DMM) is at the core of MSP. Also DMM and MSP have the worst-case complexity of the same order. So if we improve the algorithm for DMM that would also trigger the improvement of MSP. The complexity of Conventional DMM is O(n³). In the average case, All Pairs Shortest Path (APSP) Problem can be modified as a fast engine for DMM and can be solved in O(n² log n) expected time. Using this result, MSP can be solved in O(n² log² n) expected time. MSP can be extended to K-MSP. To incorporate DMM into K-MSP, DMM needs to be extended to K-DMM as well. In this research we show how DMM can be extended to K-DMM using K-Tuple Approach to solve K-MSP in O(Kn² log² n log K) time complexity when K ≤ n/log n. We also present Tournament Approach which solves K-MSP in O(n² log² n + Kn²) time complexity and outperforms the K-Tuple
13
Baniasadirad, Fatemeh [Verfasser], Florian [Akademischer Betreuer] Jarre, and Achim [Gutachter] Schädle. "On the depth of the Branch and Bound tree for solving the Maximum Stable Set Problem / Fatemeh Baniasadirad ; Gutachter: Achim Schädle ; Betreuer: Florian Jarre." Düsseldorf : Universitäts- und Landesbibliothek der Heinrich-Heine-Universität Düsseldorf, 2018. http://d-nb.info/1152076140/34.
Full text
14
Maheshwary, Siddhartha. "Facets of conflict hypergraphs." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/26635.
Full textAbstract:
Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2009.Committee Chair: Lee, Eva K.; Committee Member: Barnes, Earl; Committee Member: Johnson, Ellis; Committee Member: Parker, R. Gary; Committee Member: Wu, D. J.. Part of the SMARTech Electronic Thesis and Dissertation Collection.
15
Jin, Yan. "Hybrid metaheuristic algorithms for sum coloring and bandwidth coloring." Thesis, Angers, 2015. http://www.theses.fr/2015ANGE0062/document.
Full textAbstract:
Le problème de somme coloration minimum (MSCP) et le problème de coloration de bande passante (BCP) sont deux généralisations importantes du problème de coloration des sommets classique avec de nombreuses applications dans divers domaines, y compris la conception de circuits imprimés, la planication, l’allocation de ressource, l’affectation de fréquence dans les réseaux mobiles, etc. Les problèmes MSCP et BCP étant NP-difficiles, les heuristiques et métaheuristiques sont souvent utilisées en pratique pour obtenir des solutions de bonne qualité en un temps de calcul acceptable. Cette thèse est consacrée à des métaheuristiques hybrides pour la résolution efcace des problèmes MSCP et BCP. Pour le problème MSCP, nous présentons deux algorithmes mémétiques qui combinent l’évolution d’une population d’individus avec de la recherche locale. Pour le problème BCP, nous proposons un algorithme hybride à base d’apprentissage faisant coopérer une méthode de construction “informée” avec une procédure de recherche locale. Les algorithmes développés sont évalués sur des instances biens connues et se révèlent très compétitifs par rapport à l’état de l’art. Les principaux composants des algorithmes que nous proposons sont également analysésThe minimum sum coloring problem (MSCP) and the bandwidth coloring problem (BCP) are two important generalizations of the classical vertex coloring problem with numerous applications in diverse domains, including VLSI design, scheduling, resource allocation and frequency assignment in mobile networks, etc. Since the MSCP and BCP are NP-hard problems, heuristics and metaheuristics are practical solution methods to obtain high quality solutions in an acceptable computing time. This thesis is dedicated to developing effective hybrid metaheuristic algorithms for the MSCP and BCP. For the MSCP, we present two memetic algorithms which combine population-based evolutionary search and local search. An effective algorithm for maximum independent set is devised for generating initial solutions. For the BCP, we propose a learning-based hybrid search algorithm which follows a cooperative framework between an informed construction procedure and a local search heuristic. The proposed algorithms are evaluated on well-known benchmark instances and show highly competitive performances compared to the current state-of-the-art algorithms from the literature. Furthermore, the key issues of these algorithms are investigated and analyzed
16
MEDEIROS, Rex Antonio da Costa. "Zero-Error capacity of quantum channels." Universidade Federal de Campina Grande, 2008. http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/1320.
Full textAbstract:
Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-01T21:11:37Z
No. of bitstreams: 1
REX ANTONIO DA COSTA MEDEIROS - TESE PPGEE 2008..pdf: 1089371 bytes, checksum: ea0c95501b938e0d466779a06faaa4f6 (MD5)Made available in DSpace on 2018-08-01T21:11:37Z (GMT). No. of bitstreams: 1 REX ANTONIO DA COSTA MEDEIROS - TESE PPGEE 2008..pdf: 1089371 bytes, checksum: ea0c95501b938e0d466779a06faaa4f6 (MD5) Previous issue date: 2008-05-09
Nesta tese, a capacidade erro-zero de canais discretos sem memória é generalizada para canais quânticos. Uma nova capacidade para a transmissão de informação clássica através de canais quânticos é proposta. A capacidade erro-zero de canais quânticos (CEZQ) é definida como sendo a máxima quantidade de informação por uso do canal que pode ser enviada através de um canal quântico ruidoso, considerando uma probabilidade de erro igual a zero. O protocolo de comunicação restringe palavras-código a produtos tensoriais de estados quânticos de entrada, enquanto que medições coletivas entre várias saídas do canal são permitidas. Portanto, o protocolo empregado é similar ao protocolo de Holevo-Schumacher-Westmoreland. O problema de encontrar a CEZQ é reformulado usando elementos da teoria de grafos. Esta definição equivalente é usada para demonstrar propriedades de famílias de estados quânticos e medições que atingem a CEZQ. É mostrado que a capacidade de um canal quântico num espaço de Hilbert de dimensão d pode sempre ser alcançada usando famílias compostas de, no máximo,d estados puros. Com relação às medições, demonstra-se que medições coletivas de von Neumann são necessárias e suficientes para alcançar a capacidade. É discutido se a CEZQ é uma generalização não trivial da capacidade erro-zero clássica. O termo não trivial refere-se a existência de canais quânticos para os quais a CEZQ só pode ser alcançada através de famílias de estados quânticos não-ortogonais e usando códigos de comprimento maior ou igual a dois. É investigada a CEZQ de alguns canais quânticos. É mostrado que o problema de calcular a CEZQ de canais clássicos-quânticos é puramente clássico. Em particular, é exibido um canal quântico para o qual conjectura-se que a CEZQ só pode ser alcançada usando uma família de estados quânticos não-ortogonais. Se a conjectura é verdadeira, é possível calcular o valor exato da capacidade e construir um código de bloco quântico que alcança a capacidade. Finalmente, é demonstrado que a CEZQ é limitada superiormente pela capacidade de Holevo-Schumacher-Westmoreland.
17
Lê, Ngoc C. "Algorithms for the Maximum Independent Set Problem." Doctoral thesis, 2014. https://tubaf.qucosa.de/id/qucosa%3A22990.
Full textAbstract:
This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs.
We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in:
+ some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs);
+ some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs);
+ some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs.
Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes.
We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem.
We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs.
We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered.
Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.
18
"On exact algorithms for the maximum independent set problem." 2008. http://library.cuhk.edu.hk/record=b5896822.
Full textAbstract:
Wong, Wing Chun.Thesis (M.Phil.)--Chinese University of Hong Kong, 2008.
Includes bibliographical references (leaves 66-67).
Abstracts in English and Chinese.
Abstract --- p.i
Acknowledgement --- p.iii
Chapter 1 --- Introduction --- p.1
Chapter 2 --- Background Study --- p.4
Chapter 2.1 --- Basic Definitions and Notations --- p.5
Chapter 2.2 --- Tarjan and Trojanowski's algorithm --- p.6
Chapter 2.2.1 --- Techniques --- p.6
Chapter 2.2.2 --- Algorithm --- p.8
Chapter 2.3 --- "Fomin, Grandoni and Kratsch's Algorithm" --- p.9
Chapter 2.3.1 --- Techniques --- p.9
Chapter 2.3.2 --- Algorithm --- p.14
Chapter 3 --- Improvements --- p.18
Chapter 3.1 --- Tarjan and Trojanowski´ةs Algorithm --- p.18
Chapter 3.1.1 --- Correctness and Running Time Analysis --- p.28
Chapter 3.1.2 --- Improvement --- p.30
Chapter 3.1.3 --- Using more weights --- p.35
Chapter 3.2 --- The First Algorithm --- p.37
Chapter 3.2.1 --- Standard Analysis --- p.37
Chapter 3.2.2 --- Measure and Conquer --- p.38
Chapter 3.2.3 --- Using more weights --- p.42
Chapter 3.3 --- The Second Algorithm --- p.43
Chapter 3.3.1 --- Running Time Analysis --- p.44
Chapter 3.3.2 --- Using More Weights --- p.45
Chapter 3.4 --- The Third Algorithm --- p.46
Chapter 4 --- Lower Bounds --- p.52
Chapter 4.1 --- Tarjan and Trojanowski's Algorithm --- p.52
Chapter 4.2 --- The First Algorithm --- p.55
Chapter 4.3 --- The Second Algorithm --- p.58
Chapter 4.4 --- The Third Algorithm --- p.60
Chapter 5 --- Conclusion --- p.63
Bibliography --- p.66
19
Haieh, Tung-Ten, and 謝東諺. "Simulating Bio-molecular Operations to Solve the Maximum Independent-set Problem." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/74269157857219034432.
Full textAbstract:
碩士國立高雄應用科技大學
資訊工程系
97
With the evolution of the technological, a general computer system has to deal with the large datasets. Therefore, increasing the performance of dealing with large-scale data was remained a difficult challenge.The best way is the parallel computing besides supercomputer. The bio-molecular operations in the new field of molecular computing were a model of parallel computing. Their principles are similar to DNA activity; each cell independently works and grows. The first exhaustive search algorithm is presented from Adleman that DNA (Deoxyribonucleic Acid) experiments are used to solve the Hamiltonian path problem (HPP). Adleman’s techniques are generalized from Lipton that using them determines the satisfiability problem (SAT). Adleman and Lipton mentioned that the DNA operation can be used to develop and design many new DNA-abased algorithms for solving the NP-complete problem. Therefore, the bio-molecular operations not only can be applied to deal with huge data, but also can be employed to solve the complexity problems, such as, the maximum independent-set problem. Because of the difficulty of nanotechnology, the bio-molecular operations only work on bio laboratory. In this thesis, we used distributed systems and concept of mutli-threads to simulate the famous bio-molecular algorithm for solving the maximum independent-set problem. The result reveals that the function of each the bio-molecular operation can be performed by the proposed method. Also we compared the performance between the proposed method and those famous algorithms. From the comparison, it is indicated that the proposed method is faster those famous algorithm.
20
"Optimized crossover for the independent set problem." Alfred P. Sloan School of Management, Massachusetts Institute of Technology, 1995. http://hdl.handle.net/1721.1/2558.
Full text
21
Yan, Zhong-Gong, and 顏重功. "Solving the bottleneck independent dominating set problem on graphs." Thesis, 1991. http://ndltd.ncl.edu.tw/handle/67716505011947504832.
Full text
22
Lei, Hsing-Yi, and 雷興怡. "New Heuristics for the Maximum Bounded-Degree-d Set Problem." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/99839997550701177718.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
101
Given a graph G = (V,E), a bounded-degree-d set S is a vertex subset of G such that the maximum degree in G[S] is at most d. The MAXIMUM BOUNDED-DEGREE-d SET (MAX d-BDS) problem is to find a bounded degree-d set S of maximum cardinality in G. It is an NP-hard problem. The MAX 1-BDS problem can not be approximated to a ratio greater than n^(e−1) in polynomial time for all e > 0 unless P = NP. In this thesis,we design and implement six heuristic algorithms combined with three reduction rules. From the experiment results, we observe that our heuristic algorithms find solutions with good qualities compared with the optimal solution found by IBM ILOG CPLEX Optimizer in DIMACS graphs and with the exact algorithm given by Moser et al. in graphs from real social networks.
23
Yi-ChunSun and 孫益君. "Maximum Independent Set Algorithm with IEEE 802.11n Wireless Distribution System Performance Network." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/33020018368410366717.
Full textAbstract:
碩士國立成功大學
電機工程學系專班
100
Wireless network service and media has important for our lift. People use the wireless network to get more information and a lot fun. Wireless must has a strong signal carry to deliver data packets. If the wireless signal is not strong, the wireless transfer packets throughput will serious pitch down. IEEE 802.11n construct WDS (Wireless Distribution System) architecture, it can solve the wireless signal decline issue. The access-point can transmit data packet to other access-point on WDS architecture to keep up data packet throughput. This paper force to pitch up WDS architecture data packet throughput. This paper proposes a new algorithm (Node Degree) to calculate a NP-Problem of Maximum Independent Set to reduce calculated time on embedded system platform. The IEEE802.11n WMM parameters will depend on Node Degree algorithm to adjust value on WDS topology. This paper will develop on Embedded Linux System and modify WLAN programming to realize pitch up throughput on WDS architecture.
24
Yeh, Yu-Huan, and 葉宇桓. "A Maximum-Weight-Independent-Set-BasedAlgorithm for Reader-Coverage CollisionAvoidance Deployment in RFID Networks." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/7v5bj6.
Full textAbstract:
碩士國立高雄應用科技大學
電子工程系碩士班
102
With the rapid development of technologies in small devices, radio frequency identification(RFID) has been widely applied in many applications, such as electronic security keys, personal verification, inventory management, and logistics. In RFID system, a tag that is often attached to an item can be read in the interrogation region of a reader. The reader deployment that can provide a certain quality of services has received many attentions recently. Many researchers have studied how to deploy/activate the readers such that all of the tags in a field can be read. However, in practical environment, there exist reader-coverage collisions, and the readers often have limited readability due to the limitation of the hardware. Therefore, in the thesis, we study the problem of deploying/activating readers that have adjustable interrogation regions and limited readability, such that no reader-coverage collisions is occurred and the number of tags covered by readers is maximized, termed reader-coverage collision avoidance deployment problem. We propose a maximumweight- independent-set-based algorithm to solve the problem. In addition, we use the simulations to evaluate the performance of our proposed algorithm.
25
Wu, Guan-Han, and 巫冠翰. "An Exact Algorithm for the Densest k-set Problem on Maximum Degree Three Graphs." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/22465627778082377816.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
100
A densest k-set S in an undirected graph G=(V, E) is a vertex set of size k such that the number of edges in the subgraph induced by S is maximum among all subgraphs induced by k vertices. The concept of densest k-set is often used to define cohesive subgroups in a social network. The Densest k-Set problem is NP-hard even for graphs of maximum degree three. In this thesis, we define a variant problem of the Densest k-Set problem called the Densest Restricted k-Set problem. A vertex set S is said restricted if the graph induced by S has minimum degree at least two. The Densest Restricted k-Set problem is to find a densest k-set among all restricted vertex sets of size k. We show that if there is an algorithm that solves the Densest Restricted k-Set problem in O(f(n)) time, by taking the algorithm as a subroutine the Densest k-Set problem can be solved in time O(poly(n)*f(n)). Moreover, we give a polynomial-space algorithm running in time O*(1.7485^n) for the Densest Restricted k-Set problem on graphs of maximum degree~three.
26
Liu, Yi-Chi, and 劉奕志. "Heuristics and a Promising Branch-and-Reduce Algorithm for the Maximum Bounded-Degree-1 Set Problem." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/01896257938363790021.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
101
Given a graph G = (V, E), a bounded-degree-1 set S is a vertex subset of G such that the maximum degree in G[S] is at most one. The Maximum Bounded-Degree-1 Set "Max 1-bds" problem is to find a bounded-degree-1 set S of maximum cardinality in G. It is an NP-hard problem and can not be approximated to a ratio greater than n^{e-1} in polynomial time for all e > 0 unless P = NP. In this thesis, we design and implement heuristic algorithms and branch-and-reduce algorithms based on variant strategies. Our the branch-and-reduce algorithms apply a very simple branching rule. From the experiment results, we observe that our heuristic algorithms find solutions with good qualities, and our branch-and-reduce algorithms are more efficient than the algorithm given by Moser et al. in most of test instances.
27
Wu, Sih-Sian, and 吳思賢. "A polynomial-time approximation scheme for the minimum-weighted independent dominating set problem in wireless networks." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/45480214289912394035.
Full textAbstract:
碩士國立交通大學
應用數學系所
98
Due to different capabilities of nodes (for example, different remaining battery lives or different costs for transmitting a message) in a wireless network, it is desirable to model the underlying network topology by a node-weighted graph. A minimum-weighted independent dominating set of a node-weighted graph is a vertex subset with the minimum weight being both independent and dominating. In this thesis, we present a polynomial-time approximation scheme (PTAS) for computing a minimum-weighted independent dominating set in a node-weighted polynomially growth bounded graph, which is in a class of graphs that include the well-known unit disk graphs, unit ball graphs, and quasi unit disk graphs. To the best of our knowledge, our PTAS is the first PTAS for the minimum-weighted independent dominating set problem in wireless networks. Furthermore, when all the weights are identical, our PTAS turns out to be a simple 1-stage PTAS for computing an independent dominating set in a polynomially growth bounded graph and hence simplifies the 2-stage PTAS proposed by Hurink and Nieberg in [15].
28
Brendel, William. "From multitarget tracking to event recognition in videos." Thesis, 2011. http://hdl.handle.net/1957/21315.
Full textAbstract:
This dissertation addresses two fundamental problems in computer vision—namely,
multitarget tracking and event recognition in videos. These problems are challenging
because uncertainty may arise from a host of sources, including motion blur,
occlusions, and dynamic cluttered backgrounds. We show that these challenges can be
successfully addressed by using a multiscale, volumetric video representation, and
taking into account various constraints between events offered by domain knowledge.
The dissertation presents our two alternative approaches to multitarget tracking. The
first approach seeks to transitively link object detections across consecutive video
frames by finding the maximum independent set of a graph of all object detections.
Two maximum-independent-set algorithms are specified, and their convergence
properties theoretically analyzed. The second approach hierarchically partitions the
space-time volume of a video into tracks of objects, producing a segmentation graph of
that video. The resulting tracks encode rich contextual cues between salient video parts
in space and time, and thus facilitate event recognition, and segmentation in space and
time.
We also describe our two alternative approaches to event recognition. The first
approach seeks to learn a structural probabilistic model of an event class from training
videos represented by hierarchical segmentation graphs. The graph model is then used
for inference of event occurrences in new videos. Learning and inference algorithms
are formulated within the same framework, and their convergence rates theoretically
analyzed. The second approach to event recognition uses probabilistic first-order logic
for reasoning over continuous time intervals. We specify the syntax, learning, and
inference algorithms of this probabilistic event logic.
Qualitative and quantitative results on benchmark video datasets are also presented.
The results demonstrate that our approaches provide consistent video interpretation
with respect to acquired domain knowledge. We outperform most of the state-of-the-art
approaches on benchmark datasets. We also present our new basketball dataset that
complements existing benchmarks with new challenges.Graduation date: 2011
Access restricted to the OSU Community at author's request from May 12, 2011 - May 12, 2012
29
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.
30
Volec, Jan. "Vlastnosti grafů velkého obvodu." Master's thesis, 2011. http://www.nusl.cz/ntk/nusl-313777.
Full textAbstract:
In this work we study two random procedures in cubic graphs with large girth. The first procedure finds a probability distribution on edge-cuts such that each edge is in a randomly chosen cut with probability at least 0.88672. As corollaries, we derive lower bounds for the size of maximum cut in cubic graphs with large girth and in random cubic graphs, and also an upper bound for the fractional cut covering number in cubic graphs with large girth. The second procedure finds a probability distribution on independent sets such that each vertex is in an independent set with probability at least 0.4352. This implies lower bounds for the size of maximum independent set in cubic graphs with large girth and in random cubic graphs, as well as an upper bound for the fractional chromatic number in cubic graphs with large girth.