Log in

Relevant bibliographies by topics / Maximum Independent Set problem / Journal articles

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

Journal articles on the topic 'Maximum Independent Set problem'

Author: Grafiati

Published: 4 June 2021

Last updated: 12 February 2022

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

Select a source type:

Consult the top 50 journal articles 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 journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Luo, Dong Ling, Chen Yin Wang, Yang Yi, Dong Ling Zhang, and Xiao Cong Zhou. "Fuzzy Maximum Independent Set Problem." Applied Mechanics and Materials 687-691 (November 2014): 1161–65. http://dx.doi.org/10.4028/www.scientific.net/amm.687-691.1161.

Full text

Abstract:

Edge covering problem, dominating set problem, and independent set problem are classic problems in graph theory except for vertex covering problem. In this paper, we study the maximum independent set problem under fuzzy uncertainty environments, which aims to search for the independent set with maximum value in a graph. First, credibility theory is introduced to describe the fuzzy variable. Three decision models are performed based on the credibility theory. A hybrid intelligence algorithm which integrates genetic algorithm and fuzzy simulation is proposed due to the unavailability of traditional algorithm. Finally, numerical experiments are performed to prove the efficiency of the fuzzy decision modes and the hybrid intelligence algorithm.

APA, Harvard, Vancouver, ISO, and other styles

2

Luo, Dong Ling, Chen Yin Wang, Yang Yi, Dong Ling Zhang, and Xiao Cong Zhou. "Fuzzy Maximum Independent Set Problem of Graphic." Applied Mechanics and Materials 687-691 (November 2014): 1657–61. http://dx.doi.org/10.4028/www.scientific.net/amm.687-691.1657.

Full text

Abstract:

Edge covering problem, dominating set problem, and independent set problem are classic problems in graph theory except for vertex covering problem. In this paper, we study the maximum independent set problem under fuzzy uncertainty environments, which aims to search for the independent set with maximum value in a graph. First, credibility theory is introduced to describe the fuzzy variable. Three decision models are performed based on the credibility theory. A hybrid intelligence algorithm which integrates genetic algorithm and fuzzy simulation is proposed due to the unavailability of traditional algorithm. Finally, numerical experiments are performed to prove the efficiency of the fuzzy decision modes and the hybrid intelligence algorithm.

APA, Harvard, Vancouver, ISO, and other styles

3

FAN, Yue-Ke, Xiao-Li Qiang, and Jin XU. "Sticker Model for Maximum Clique Problem and Maximum Independent Set." Chinese Journal of Computers 33, no. 2 (April 27, 2010): 305–10. http://dx.doi.org/10.3724/sp.j.1016.2010.00305.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Yang, Yan, and Zhi Xiang Yin. "Surface- Based Computing Model of Maximum Independent Set Problem." Advanced Materials Research 328-330 (September 2011): 1729–33. http://dx.doi.org/10.4028/www.scientific.net/amr.328-330.1729.

Full text

Abstract:

About thirty years ago, the concept of the complexity of the problem was proposed. The most important complex class is P and NP class. Fruitful results of this concept are the existence of the so-called complex class complete problem. If the other issues of this class once solved in polynomial time, then the problem must exist polynomial time algorithms. Therefore, the complete problem is most difficult to solve, but because of their presence, we can choose any of them improved algorithm for a problem, so this kind of problem to get a good solution. DNA computing is a novel method that solving a class of intractable computational problems, in which the computing speeds up exponentially with the problem size. Up to now, many accomplishments have been made to improve its performance and increase its reliability. Maximum Independent Set problem (MIS) is a well-known NP-complete problem. Maximum Clique and Minimum Vertex Covering problem is equivalent to Maximum Independent Set problem. In this paper, we explore solving Maximum Independent Set problem by transforming it into equivalent 0-1 programming problem, and utilizing the surface computing model of that. The proposed method demonstrates universal nature of NP-complete problem.

APA, Harvard, Vancouver, ISO, and other styles

5

Saha, Anita, and Madhumangal Pal. "Maximum weightk-independent set problem on permutation graphs." International Journal of Computer Mathematics 80, no. 12 (December 2003): 1477–87. http://dx.doi.org/10.1080/00207160310001614972.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Andrade, Diogo V., Mauricio G. C. Resende, and Renato F. Werneck. "Fast local search for the maximum independent set problem." Journal of Heuristics 18, no. 4 (February 25, 2012): 525–47. http://dx.doi.org/10.1007/s10732-012-9196-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Burns, James E. "The maximum independent set problem for cubic planar graphs." Networks 19, no. 3 (May 1989): 373–78. http://dx.doi.org/10.1002/net.3230190307.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

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

11

Lê, Ngoc C., and Trung Tran. "On the Maximum Independent Set Problem in Graphs of Bounded Maximum Degree." Acta Mathematica Vietnamica 45, no. 2 (June 2020): 463–75. http://dx.doi.org/10.1007/s40306-020-00368-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

BEREG, SERGEY, ADRIAN DUMITRESCU, and MINGHUI JIANG. "MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS." International Journal of Computational Geometry & Applications 20, no. 02 (April 2010): 105–18. http://dx.doi.org/10.1142/s0218195910003220.

Full text

Abstract:

Maximum Independent Set (MIS) and its relative Maximum Weight Independent Set (MWIS) are well-known problems in combinatorial optimization; they are NP-hard even in the geometric setting of unit disk graphs. In this paper, we study the Maximum Area Independent Set (MAIS) problem, a natural restricted version of MWIS in disk intersection graphs where the weight equals the disk area. We obtain: (i) Quantitative bounds on the maximum total area of an independent set relative to the union area; (ii) Practical constant-ratio approximation algorithms for finding an independent set with a large total area relative to the union area.

APA, Harvard, Vancouver, ISO, and other styles

13

Brause, Christoph, Ngoc C. Le, and Ingo Schiermeyer. "On sequential heurestic methods for the maximum independent set problem." Discussiones Mathematicae Graph Theory 37, no. 2 (2017): 415. http://dx.doi.org/10.7151/dmgt.1965.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Murat, Cécile, and Vangelis Th Paschos. "A priori optimization for the probabilistic maximum independent set problem." Theoretical Computer Science 270, no. 1-2 (January 2002): 561–90. http://dx.doi.org/10.1016/s0304-3975(01)00005-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Butenko, Sergiy, and Svyatoslav Trukhanov. "Using critical sets to solve the maximum independent set problem." Operations Research Letters 35, no. 4 (July 2007): 519–24. http://dx.doi.org/10.1016/j.orl.2006.07.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Tang Jian. "An O(20.304n) Algorithm for Solving Maximum Independent Set Problem." IEEE Transactions on Computers C-35, no. 9 (September 1986): 847–51. http://dx.doi.org/10.1109/tc.1986.1676847.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Shiraishi, Naoto, and Jun Takahashi. "Constructing concrete hard instances of the maximum independent set problem." Journal of Statistical Mechanics: Theory and Experiment 2019, no. 11 (November 4, 2019): 113401. http://dx.doi.org/10.1088/1742-5468/ab409d.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Paschos, V. Th. "A ( °/2) -approximation algorithm for the maximum independent set problem." Information Processing Letters 44, no. 1 (November 1992): 11–13. http://dx.doi.org/10.1016/0020-0190(92)90248-t.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Brause, Christoph, Ngoc Chi Lê, and Ingo Schiermeyer. "The Maximum Independent Set Problem in Subclasses of Subcubic Graphs." Discrete Mathematics 338, no. 10 (October 2015): 1766–78. http://dx.doi.org/10.1016/j.disc.2015.01.041.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Barbosa, Valmir C., and Luciana C. D. Campos. "A Novel Evolutionary Formulation of the Maximum Independent Set Problem." Journal of Combinatorial Optimization 8, no. 4 (December 2004): 419–37. http://dx.doi.org/10.1007/s10878-004-4835-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Liu, Shuaifu, and Zhao Zhang. "The 0–1 inverse maximum independent set problem on forests and unicyclic graphs." Discrete Mathematics, Algorithms and Applications 08, no. 02 (May 26, 2016): 1650019. http://dx.doi.org/10.1142/s1793830916500191.

Full text

Abstract:

Given a graph [Formula: see text] and an independent set [Formula: see text] of [Formula: see text], the 0–1 inverse maximum independent set problem (IMIS[Formula: see text]) is to delete as few vertices as possible such that [Formula: see text] becomes a maximum independent set of [Formula: see text]. It is known that IMIS[Formula: see text] is NP-hard even when the given independent set has a bounded size. In this paper, we present linear-time algorithms for IMIS[Formula: see text] on forests and unicyclic graphs.

APA, Harvard, Vancouver, ISO, and other styles

22

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

23

Ugurlu, Onur. "A New Heuristic Algorithm to Solve the Maximum Independent Set Problem." Mathematical and Computational Applications 18, no. 3 (December 1, 2013): 495–501. http://dx.doi.org/10.3390/mca18030495.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Douiri, Sidi Mohamed, and Souad Elbernoussi. "An unconstrained binary quadratic programming for the maximum independent set problem." Nonlinear Analysis: Modelling and Control 17, no. 4 (October 25, 2012): 410–17. http://dx.doi.org/10.15388/na.17.4.14047.

Full text

Abstract:

For a given graph G = (V, E) the maximum independent set problem is to find the largest subset of pairwise nonadjacent vertices. We propose a new model which is a reformulation of the maximum independent set problem as an unconstrained quadratic binary programming, and we resolve it afterward by means of a genetic algorithm. The efficiency of the approach is confirmed by results of numerical experiments on DIMACS benchmarks.

APA, Harvard, Vancouver, ISO, and other styles

25

Lozin, Vadim, and Martin Milanič. "On the Maximum Independent Set Problem in Subclasses of Planar Graphs." Journal of Graph Algorithms and Applications 14, no. 2 (2010): 269–86. http://dx.doi.org/10.7155/jgaa.00207.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Adil, Bouhouch, Loqman Chakir, and El Qadi Abderrahime. "CHN and Swap Heuristic to Solve the Maximum Independent Set Problem." International Journal of Electrical and Computer Engineering (IJECE) 7, no. 6 (December 1, 2017): 3583. http://dx.doi.org/10.11591/ijece.v7i6.pp3583-3592.

Full text

Abstract:

<p>We describe a new approach to solve the problem to find the maximum independent set in a given Graph, known also as Max-Stable set problem (MSSP). In this paper, we show how Max-Stable problem can be reformulated into a linear problem under quadratic constraints, and then we resolve the QP result by a hybrid approach based Continuous Hopfeild Neural Network (CHN) and Local Search. In a manner that the solution given by the CHN will be the starting point of the local search. The new approach showed a good performance than the original one which executes a suite of CHN runs, at each execution a new leaner constraint is added into the resolved model. To prove the efficiency of our approach, we present some computational experiments of solving random generated problem and typical MSSP instances of real life problem.</p>

APA, Harvard, Vancouver, ISO, and other styles

27

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Huang, Yufang, Jianhua Xiao, Keqin Jiang, and Zhihua Chen. "Parallel Solution for Maximum Independent Set Problem by Programmable Tile Assembly." Chinese Journal of Electronics 25, no. 2 (March 1, 2016): 203–8. http://dx.doi.org/10.1049/cje.2016.03.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Wang, Zhaocai, Jian Tan, Lanwei Zhu, and Wei Huang. "Solving the Maximum Independent Set Problem based on Molecule Parallel Supercomputing." Applied Mathematics & Information Sciences 8, no. 5 (September 1, 2014): 2361–66. http://dx.doi.org/10.12785/amis/080531.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Lozin, Vadim V., Martin Milanič, and Christopher Purcell. "Graphs Without Large Apples and the Maximum Weight Independent Set Problem." Graphs and Combinatorics 30, no. 2 (November 15, 2012): 395–410. http://dx.doi.org/10.1007/s00373-012-1263-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Zhang, Cheng, Jing Yang, Jin Xu, and DongMing Zhao. "A DNA length reducing computing model for maximum independent set problem." Chinese Science Bulletin 55, no. 9 (March 2010): 890–96. http://dx.doi.org/10.1007/s11434-009-0608-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Lozin, Vadim, Jérôme Monnot, and Bernard Ries. "On the maximum independent set problem in subclasses of subcubic graphs." Journal of Discrete Algorithms 31 (March 2015): 104–12. http://dx.doi.org/10.1016/j.jda.2014.08.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Wang, Jiahai, Zheng Tang, and Xinshun Xu. "Maximum Neural Network with Nonlinear Self-Feedback and Its Application to Maximum Independent Set Problem." IEEJ Transactions on Electronics, Information and Systems 125, no. 2 (2005): 314–20. http://dx.doi.org/10.1541/ieejeiss.125.314.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Alidaee, Bahram, Gary Kochenberger, and Haibo Wang. "Simple and fast surrogate constraint heuristics for the maximum independent set problem." Journal of Heuristics 14, no. 6 (October 24, 2007): 571–85. http://dx.doi.org/10.1007/s10732-007-9054-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

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 (March 2003): 313–22. http://dx.doi.org/10.1016/s0166-218x(02)00205-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Klobučar, Ana, and Robert Manger. "Solving Robust Variants of the Maximum Weighted Independent Set Problem on Trees." Mathematics 8, no. 2 (February 20, 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

37

Alipour, Mir Mohammad, and Mohsen Abdolhosseinzadeh. "A multiagent reinforcement learning algorithm to solve the maximum independent set problem." Multiagent and Grid Systems 16, no. 1 (April 9, 2020): 101–15. http://dx.doi.org/10.3233/mgs-200323.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Lê, Ngoc C., Christoph Brause, and Ingo Schiermeyer. "The Maximum Independent Set Problem in Subclasses ofSi,j,k-Free Graphs." Electronic Notes in Discrete Mathematics 49 (November 2015): 43–49. http://dx.doi.org/10.1016/j.endm.2015.06.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Karthick, T. "On atomic structure ofP5-free subclasses and Maximum Weight Independent Set problem." Theoretical Computer Science 516 (January 2014): 78–85. http://dx.doi.org/10.1016/j.tcs.2013.11.019.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Zhou, Kang, Yingying Duan, Wenbo Dong, and Qinhong Fu. "A Matrix Algorithm for Maximum Independent Set Problem Based on Sticker Model." Journal of Computational and Theoretical Nanoscience 13, no. 6 (June 1, 2016): 3734–43. http://dx.doi.org/10.1166/jctn.2016.5205.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Warrier, Deepak, Wilbert E. Wilhelm, Jeffrey S. Warren, and Illya V. Hicks. "A branch-and-price approach for the maximum weight independent set problem." Networks 46, no. 4 (2005): 198–209. http://dx.doi.org/10.1002/net.20088.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Du, Peng, and Yuan Zhang. "A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem." Mathematical Problems in Engineering 2016 (2016): 1–10. http://dx.doi.org/10.1155/2016/9790629.

Full text

Abstract:

Maximum weight independent set (MWIS) is a combinatorial optimization problem that naturally arises in many applications especially wireless networking. This paper studies distributed approximation algorithms for finding MWIS in a general graph. In the proposed algorithm, each node keeps exchanging messages with neighbors in which each message contains partial solutions of the MWIS optimization program. A parameterHis introduced to achieve different tradeoff between approximation accuracy and space complexity. Theoretical analysis shows that the proposed algorithm is guaranteed to converge to an approximate solution after finite iterations; specifically, the proposed algorithm is guaranteed to converge to the optimal solution withH=+∞. Simulation results confirm the effectiveness of the proposed distributed algorithm in terms of weight sum, message size, and convergence performance.

APA, Harvard, Vancouver, ISO, and other styles

43

XU, XINSHUN, ZHENG TANG, and JIAHAI WANG. "AN IMPROVED TRANSIENTLY CHAOTIC NEURAL NETWORK FOR THE MAXIMUM INDEPENDENT SET PROBLEM." International Journal of Neural Systems 14, no. 06 (December 2004): 381–92. http://dx.doi.org/10.1142/s0129065704002133.

Full text

Abstract:

By analyzing the dynamic behaviors of the transiently chaotic neural network and greedy heuristic for the maximum independent set (MIS) problem, we present an improved transiently chaotic neural network for the MIS problem in this paper. Extensive simulations are performed and the results show that this proposed transiently chaotic neural network can yield better solutions to p-random graphs than other existing algorithms. The efficiency of the new model is also confirmed by the results on the complement graphs of some DIMACS clique instances in the second DIMACS challenge. Moreover, the improved model uses fewer steps to converge to stable state in comparison with the original transiently chaotic neural network.

APA, Harvard, Vancouver, ISO, and other styles

44

Keil, J. Mark, Joseph S. B. Mitchell, Dinabandhu Pradhan, and Martin Vatshelle. "An algorithm for the maximum weight independent set problem on outerstring graphs." Computational Geometry 60 (January 2017): 19–25. http://dx.doi.org/10.1016/j.comgeo.2016.05.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Hsiao, Ju Yuan, Chuan Yi Tang, and Ruay Shiung Chang. "Solving the single step graph searching problem by solving the maximum two-independent set problem." Information Processing Letters 40, no. 5 (December 1991): 283–87. http://dx.doi.org/10.1016/0020-0190(91)90124-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Saleem, Zain Hamid. "Max-independent set and the quantum alternating operator ansatz." International Journal of Quantum Information 18, no. 04 (June 2020): 2050011. http://dx.doi.org/10.1142/s0219749920500112.

Full text

Abstract:

The maximum-independent set (MIS) problem of graph theory using the quantum alternating operator ansatz is studied. We perform simulations on the Rigetti Forest simulator for the square ring, [Formula: see text], and [Formula: see text] graphs and analyze the dependence of the algorithm on the depth of the circuit and initial states. The probability distribution of observation of the feasible states representing maximum-independent sets is observed to be asymmetric for the MIS problem, which is unlike the Max-Cut problem where the probability distribution of feasible states is symmetric. For asymmetric graphs, it is shown that the algorithm clearly favors the independent set with the larger number of elements even for finite circuit depth. We also compare the approximation ratios for the algorithm when we choose different initial states for the square ring graph and show that it is dependent on the choice of the initial state.

APA, Harvard, Vancouver, ISO, and other styles

47

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

48

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/isprs-archives-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

49

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Beke, Ákos, Sándor Szabó, and Bogdán Zavalnij. "Some Zero-One Linear Programming Reformulations for the Maximum Clique Problem." Mathematica Pannonica 27_NS1, no. 1 (April 8, 2021): 32–47. http://dx.doi.org/10.1556/314.2020.00005.

Full text

Abstract:

Many combinatorial optimization problems can be expressed in terms of zero-one linear programs. For the maximum clique problem the so-called edge reformulation is applied most commonly. Two less frequently used LP equivalents are the independent set and edge covering set reformulations. The number of the constraints (as a function of the number of vertices of the ground graph) is asymptotically quadratic in the edge and the edge covering set LP reformulations and it is exponential in the independent set reformulation, respectively. F. D. Croce and R. Tadei proposed an approach in which the number of the constraints is equal to the number of the vertices. In this paper we are looking for possible tighter variants of these linear programs.

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!