Relevant bibliographies by topics / Maximum weighted independent set problem

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Maximum weighted independent set problem'

Author: Grafiati
Published: 4 June 2021
Last updated: 9 February 2022

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Maximum weighted 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.

Journal articles on the topic "Maximum weighted independent set problem"

1

Wang, Yanfeng, Xuewen Bai, Donghui Wei, and Guangzhao Cui. "DNA Self-Assembly for Maximum Weighted Independent Set Problem." Advanced Science Letters 17, no. 1 (2012): 21–26. http://dx.doi.org/10.1166/asl.2012.3677.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Yu, Chang-Wu, and Gen-Huey Chen. "The weighted maximum independent set problem in permutation graphs." BIT 32, no. 4 (1992): 609–18. http://dx.doi.org/10.1007/bf01994845.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Li, Ruizhi, Yupan Wang, Shuli Hu, Jianhua Jiang, Dantong Ouyang, and Minghao Yin. "Solving the Set Packing Problem via a Maximum Weighted Independent Set Heuristic." Mathematical Problems in Engineering 2020 (December 16, 2020): 1–11. http://dx.doi.org/10.1155/2020/3050714.

Full text
Abstract:
The set packing problem (SPP) is a significant NP-hard combinatorial optimization problem with extensive applications. In this paper, we encode the set packing problem as the maximum weighted independent set (MWIS) problem and solve the encoded problem with an efficient algorithm designed to the MWIS problem. We compare the independent set-based method with the state-of-the-art algorithms for the set packing problem on the 64 standard benchmark instances. The experimental results show that the independent set-based method is superior to the existing algorithms in terms of the quality of the solutions and running time obtained the solutions.
APA, Harvard, Vancouver, ISO, and other styles
4

Klobučar, Ana, and Robert Manger. "An evolutionary algorithm for the robust maximum weighted independent set problem." Automatika 61, no. 4 (2020): 523–36. http://dx.doi.org/10.1080/00051144.2020.1789364.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Talla Nobibon, Fabrice, and Roel Leus. "Robust maximum weighted independent-set problems on interval graphs." Optimization Letters 8, no. 1 (2012): 227–35. http://dx.doi.org/10.1007/s11590-012-0563-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Sakai, Shuichi, Mitsunori Togasaki, and Koichi Yamazaki. "A note on greedy algorithms for the maximum weighted independent set problem." Discrete Applied Mathematics 126, no. 2-3 (2003): 313–22. http://dx.doi.org/10.1016/s0166-218x(02)00205-6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Klobučar, Ana, and Robert Manger. "Solving Robust Variants of the Maximum Weighted Independent Set Problem on Trees." Mathematics 8, no. 2 (2020): 285. http://dx.doi.org/10.3390/math8020285.

Full text
Abstract:
This paper deals with the maximum weighted independent set (MWIS) problem. We consider several robust variants of the MWIS problem on trees and prove that most of them are NP-hard. We propose a heuristic for solving the considered robust MWIS variants, which is customized for trees. We demonstrate by experiments that our algorithm produces high-quality solutions and runs much faster than a general-purpose optimization software.
APA, Harvard, Vancouver, ISO, and other styles
8

LEE, D. T., and MAJID SARRAFZADEH. "MAXIMUM INDEPENDENT SET OF A PERMUTATION GRAPH IN K TRACKS." International Journal of Computational Geometry & Applications 03, no. 03 (1993): 291–304. http://dx.doi.org/10.1142/s021819599300018x.

Full text
Abstract:
A maximum weighted independent set of a permutation graph is a maximum subset of noncrossing chords in a matching diagram (i.e., a set Φ of chords with end-points on two horizontal lines). The problem of finding, among all noncrossing subsets of Φ with density at most k, one with maximum size is considered, where the density of a subset is the maximum number of chords crossing a vertical line and k is a given parameter. A Θ(n log n) time and Θ(n) space algorithm, for solving the problem with n chords, is proposed. As an application, we solve the problem of finding, among all proper subsets with density at most k of an interval graph, one with maximum number of intervals.
APA, Harvard, Vancouver, ISO, and other styles
9

Demange, Marc, Bernard Kouakou, and Eric Soutif. "On-line computation and maximum-weighted hereditary subgraph problems." Yugoslav Journal of Operations Research 21, no. 1 (2011): 11–28. http://dx.doi.org/10.2298/yjor1101011d.

Full text
Abstract:
In this paper1 we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance (a graph with n vertices) is revealed in t clusters, 2 ? t ? n . We first focus on an on-line version of the maximumweighted hereditary subgraph problem. Then, we deal with the particular case of the independent set problem. We are interested in two types of results: the competitive ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them.
APA, Harvard, Vancouver, ISO, and other styles
10

Haunert, Jan-Henrik, and Alexander Wolff. "BEYOND MAXIMUM INDEPENDENT SET: AN EXTENDED MODEL FOR POINT-FEATURE LABEL PLACEMENT." ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XLI-B2 (June 7, 2016): 109–14. http://dx.doi.org/10.5194/isprsarchives-xli-b2-109-2016.

Full text
Abstract:
Map labeling is a classical problem of cartography that has frequently been approached by combinatorial optimization. Given a set of features in the map and for each feature a set of label candidates, a common problem is to select an independent set of labels (that is, a labeling without label–label overlaps) that contains as many labels as possible and at most one label for each feature. To obtain solutions of high cartographic quality, the labels can be weighted and one can maximize the total weight (rather than the number) of the selected labels. We argue, however, that when maximizing the weight of the labeling, interdependences between labels are insufficiently addressed. Furthermore, in a maximum-weight labeling, the labels tend to be densely packed and thus the map background can be occluded too much. We propose extensions of an existing model to overcome these limitations. Since even without our extensions the problem is NP-hard, we cannot hope for an efficient exact algorithm for the problem. Therefore, we present a formalization of our model as an integer linear program (ILP). This allows us to compute optimal solutions in reasonable time, which we demonstrate for randomly generated instances.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Maximum weighted independent set problem"

1

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 text
Abstract:
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.<br>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.
APA, Harvard, Vancouver, ISO, and other styles
2

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
3

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

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
APA, Harvard, Vancouver, ISO, and other styles
5

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
6

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
APA, Harvard, Vancouver, ISO, and other styles
7

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
APA, Harvard, Vancouver, ISO, and other styles
8

Morel, Gregory. "Stabilité et coloration des graphes sans P5." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENM042/document.

Full text
Abstract:
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 artificielle<br>The 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
APA, Harvard, Vancouver, ISO, and other styles
9

Lê, Ngoc C. "Algorithms for the Maximum Independent Set Problem." Doctoral thesis, 2014. https://tubaf.qucosa.de/id/qucosa%3A22990.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
10

"On exact algorithms for the maximum independent set problem." 2008. http://library.cuhk.edu.hk/record=b5896822.

Full text
Abstract:
Wong, Wing Chun.<br>Thesis (M.Phil.)--Chinese University of Hong Kong, 2008.<br>Includes bibliographical references (leaves 66-67).<br>Abstracts in English and Chinese.<br>Abstract --- p.i<br>Acknowledgement --- p.iii<br>Chapter 1 --- Introduction --- p.1<br>Chapter 2 --- Background Study --- p.4<br>Chapter 2.1 --- Basic Definitions and Notations --- p.5<br>Chapter 2.2 --- Tarjan and Trojanowski's algorithm --- p.6<br>Chapter 2.2.1 --- Techniques --- p.6<br>Chapter 2.2.2 --- Algorithm --- p.8<br>Chapter 2.3 --- "Fomin, Grandoni and Kratsch's Algorithm" --- p.9<br>Chapter 2.3.1 --- Techniques --- p.9<br>Chapter 2.3.2 --- Algorithm --- p.14<br>Chapter 3 --- Improvements --- p.18<br>Chapter 3.1 --- Tarjan and Trojanowski´ةs Algorithm --- p.18<br>Chapter 3.1.1 --- Correctness and Running Time Analysis --- p.28<br>Chapter 3.1.2 --- Improvement --- p.30<br>Chapter 3.1.3 --- Using more weights --- p.35<br>Chapter 3.2 --- The First Algorithm --- p.37<br>Chapter 3.2.1 --- Standard Analysis --- p.37<br>Chapter 3.2.2 --- Measure and Conquer --- p.38<br>Chapter 3.2.3 --- Using more weights --- p.42<br>Chapter 3.3 --- The Second Algorithm --- p.43<br>Chapter 3.3.1 --- Running Time Analysis --- p.44<br>Chapter 3.3.2 --- Using More Weights --- p.45<br>Chapter 3.4 --- The Third Algorithm --- p.46<br>Chapter 4 --- Lower Bounds --- p.52<br>Chapter 4.1 --- Tarjan and Trojanowski's Algorithm --- p.52<br>Chapter 4.2 --- The First Algorithm --- p.55<br>Chapter 4.3 --- The Second Algorithm --- p.58<br>Chapter 4.4 --- The Third Algorithm --- p.60<br>Chapter 5 --- Conclusion --- p.63<br>Bibliography --- p.66
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Maximum weighted independent set problem"

1

Li, Qingyan, Zhixiang Yin, and Min Chen. "Closed Circle DNA Algorithm of Maximum Weighted Independent Set Problem." In Proceedings of The Eighth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 2013. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-37502-6_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Gellner, Alexander, Sebastian Lamm, Christian Schulz, Darren Strash, and Bogdán Zaválnij. "Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations." In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, 2021. http://dx.doi.org/10.1137/1.9781611976472.10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Lamm, Sebastian, Christian Schulz, Darren Strash, Robert Williger, and Huashuo Zhang. "Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs." In 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, 2019. http://dx.doi.org/10.1137/1.9781611975499.12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Papageorgiou, Dimitri J., and Michael R. Salpukas. "The Maximum Weight Independent Set Problem for Data Association in Multiple Hypothesis Tracking." In Optimization and Cooperative Control Strategies. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-540-88063-9_15.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Valiente, Gabriel. "A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs." In Algorithms and Computation. Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-24587-2_15.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Chudnovsky, Maria, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé. "Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs." In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2020. http://dx.doi.org/10.1137/1.9781611975994.139.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Kako, Akihisa, Takao Ono, Tomio Hirata, and Magnús M. Halldórsson. "Approximation Algorithms for the Weighted Independent Set Problem." In Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11604686_30.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Xu, Xiaohua, Shaojie Tang, and Peng-Jun Wan. "Maximum Weighted Independent Set of Links under Physical Interference Model." In Wireless Algorithms, Systems, and Applications. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14654-1_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Demange, Marc, and Vangelis Th Paschos. "Constructive — non-constructive approximation and maximum independent set problem." In Combinatorics and Computer Science. Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/3-540-61576-8_83.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Andrade, Diogo V., Mauricio G. C. Resende, and Renato F. Werneck. "Fast Local Search for the Maximum Independent Set Problem." In Experimental Algorithms. Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-68552-4_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Maximum weighted independent set problem"

1

Atsuta, Yoshito, and Satoshi Takahashi. "The maximum weighted k distance-d independent set problem on interval graph." In 2020 9th International Congress on Advanced Applied Informatics (IIAI-AAI). IEEE, 2020. http://dx.doi.org/10.1109/iiai-aai50415.2020.00177.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Schnorr, Andrea, Dirk N. Helmrich, Hank Childs, Torsten W. Kuhlen, and Bernd Hentschel. "Feature Tracking Utilizing a Maximum-Weight Independent Set Problem." In 2019 IEEE 9th Symposium on Large Data Analysis and Visualization (LDAV). IEEE, 2019. http://dx.doi.org/10.1109/ldav48142.2019.8944363.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Gamarnik, David, David Goldberg, and Theophane Weber. "PTAS for maximum weight independent set problem with random weights in bounded degree graphs." In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2010. http://dx.doi.org/10.1137/1.9781611973075.23.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Wang, Peng, and Stephan Bohacek. "On the practical complexity of solving the maximum weighted independent set problem for optimal scheduling in wireless networks." In 4th International ICST Conference on Wireless Internet. ICST, 2008. http://dx.doi.org/10.4108/icst.wicon2008.4862.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Cai, Shaowei, Wenying Hou, Jinkun Lin, and Yuanjie Li. "Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/196.

Full text
Abstract:
The minimum weight vertex cover (MWVC) problem is an important combinatorial optimization problem with various real-world applications. Due to its NP hardness, most works on solving MWVC focus on heuristic algorithms that can return a good quality solution in reasonable time. In this work, we propose two dynamic strategies that adjust the behavior of the algorithm during search, which are used to improve a state of the art local search for MWVC named FastWVC, resulting in two local search algorithms called DynWVC1 and DynWVC2. Previous MWVC algorithms are evaluated on graphs with random or hand crafted weights. In this work, we evaluate the algorithms on the vertex weighted graphs that obtained from an important real world problem, the map labeling problem. Experiments show that our algorithm obtains better results than previous algorithms for MWVC and maximum weight independent set (MWIS) on these real world instances. We also test our algorithms on massive graphs studied in previous works, and show significant improvements there.
APA, Harvard, Vancouver, ISO, and other styles
6

Li, Zhonghua, and Guannan He. "Maximum Weighted Independent Set Based RFID Reader Anti-Collision Protocol." In 2020 39th Chinese Control Conference (CCC). IEEE, 2020. http://dx.doi.org/10.23919/ccc50068.2020.9188648.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Xiao, Mingyu, Sen Huang, Yi Zhou, and Bolin Ding. "Efficient Reductions and a Fast Algorithm of Maximum Weighted Independent Set." In WWW '21: The Web Conference 2021. ACM, 2021. http://dx.doi.org/10.1145/3442381.3450130.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Gu, Jiewei, Weiguo Zheng, Yuzheng Cai, and Peng Peng. "Towards Computing a Near-Maximum Weighted Independent Set on Massive Graphs." In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, 2021. http://dx.doi.org/10.1145/3447548.3467232.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Taranenko, A., and A. Vesel. "An elitist genetic algorithm for the maximum independent set problem." In Proceedings 23rd International Conference Information Technology Interfaces. ITI 2001. IEEE, 2001. http://dx.doi.org/10.1109/iti.2001.938044.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Deng, Changshou, Yanlin Yang, and Hu Peng. "Structure-encoding Differential Evolution for the Maximum Independent Set Problem." In 2011 Fourth International Workshop on Advanced Computational Intelligence (IWACI). IEEE, 2011. http://dx.doi.org/10.1109/iwaci.2011.6159997.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Maximum weighted independent set problem' for particular source types:
Journal articles
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!

To the bibliography