Log in

Relevant bibliographies by topics / Weighted vertex cover / Journal articles

To see the other types of publications on this topic, follow the link: Weighted vertex cover.

Journal articles on the topic 'Weighted vertex cover'

Author: Grafiati

Published: 3 June 2025

Last updated: 31 July 2025

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 'Weighted vertex cover.'

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

Hend Elmorsy. "Minimum Weighted Vertex Cover on Difference Graphs and It's Algorithm." Metallurgical and Materials Engineering 31, no. 4 (2025): 906–9. https://doi.org/10.63278/1532.

Full text

Abstract:

Let µ(G) and γ(G) be vertex covering number and independent number of G. In this paper compute minimum vertex cover on weighted vertex different graphs. An effective algorithm is illustrated to find minimum weighted vertex cover.

APA, Harvard, Vancouver, ISO, and other styles

2

Zhang, Yong, and Hong Zhu. "Approximation algorithm for weighted weak vertex cover." Journal of Computer Science and Technology 19, no. 6 (2004): 782–86. http://dx.doi.org/10.1007/bf02973439.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Grandoni, Fabrizio, Jochen Könemann, and Alessandro Panconesi. "Distributed weighted vertex cover via maximal matchings." ACM Transactions on Algorithms 5, no. 1 (2008): 1–12. http://dx.doi.org/10.1145/1435375.1435381.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Wei, Hao-Ting, Wing-Kai Hon, Paul Horn, Chung-Shou Liao, and Kunihiko Sadakane. "Approximating Dynamic Weighted Vertex Cover with Soft Capacities." Algorithmica 84, no. 1 (2021): 124–49. http://dx.doi.org/10.1007/s00453-021-00886-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Brešar, B., R. Krivoš-Belluš, G. Semanišin, and P. Šparl. "On the weighted k-path vertex cover problem." Discrete Applied Mathematics 177 (November 2014): 14–18. http://dx.doi.org/10.1016/j.dam.2014.05.042.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Pourhassan, Mojgan, Feng Shi, and Frank Neumann. "Parameterized Analysis of Multiobjective Evolutionary Algorithms and the Weighted Vertex Cover Problem." Evolutionary Computation 27, no. 4 (2019): 559–75. http://dx.doi.org/10.1162/evco_a_00255.

Full text

Abstract:

Evolutionary multiobjective optimization for the classical vertex cover problem has been analysed in Kratsch and Neumann ( 2013 ) in the context of parameterized complexity analysis. This article extends the analysis to the weighted vertex cover problem in which integer weights are assigned to the vertices and the goal is to find a vertex cover of minimum weight. Using an alternative mutation operator introduced in Kratsch and Neumann ( 2013 ), we provide a fixed parameter evolutionary algorithm with respect to [Formula: see text], the cost of an optimal solution for the problem. Moreover, we

APA, Harvard, Vancouver, ISO, and other styles

7

Niedermeier, Rolf, and Peter Rossmanith. "On efficient fixed-parameter algorithms for weighted vertex cover." Journal of Algorithms 47, no. 2 (2003): 63–77. http://dx.doi.org/10.1016/s0196-6774(03)00005-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Chlebík, Miroslav, and Janka Chlebíková. "Crown reductions for the Minimum Weighted Vertex Cover problem." Discrete Applied Mathematics 156, no. 3 (2008): 292–312. http://dx.doi.org/10.1016/j.dam.2007.03.026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Yiu, Cheuk Hei Josh. "Research on Matching and Vertex Cover Problems in Bipartite Graphs using Simplex Method." Highlights in Science, Engineering and Technology 38 (March 16, 2023): 82–89. http://dx.doi.org/10.54097/hset.v38i.5737.

Full text

Abstract:

This paper considers a bipartite graph where a perfect matching does not necessarily exist. Linear programming is used in this paper as a special case of the linear program is the assignment problem, which is another name for the weighted maximum matching problem. The objective is to show that linear programming, in particular the simplex algorithm, can be used to calculate maximum weight matchings and minimum weighted vertex covers. This study also calculates and shows the equivalence of the maximum matching and minimum vertex cover cardinalities, and uses linear programming duality to presen

APA, Harvard, Vancouver, ISO, and other styles

10

Likas, Aristidis, and Andreas Stafylopatis. "A parallel algorithm for the minimum weighted vertex cover problem." Information Processing Letters 53, no. 4 (1995): 229–34. http://dx.doi.org/10.1016/0020-0190(94)00189-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

McSorley, John P., and Philip Feinsilver. "The m-Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences." International Journal of Combinatorics 2014 (January 12, 2014): 1–13. http://dx.doi.org/10.1155/2014/258017.

Full text

Abstract:

An m-path cover Γ={Pℓ1,Pℓ2,…,Pℓr} of a simple graph G is a set of vertex disjoint paths of G, each with ℓk≤m vertices, that span G. With every Pℓ we associate a weight, ω(Pℓ), and define the weight of Γ to be ω(Γ)=∏k=1r‍ω(Pℓk). The m-path cover polynomial of G is then defined as ℙm(G)=∑Γ‍ω(Γ), where the sum is taken over all m-path covers Γ of G. This polynomial is a specialization of the path-cover polynomial of Farrell. We consider the m-path cover polynomial of a weighted path P(m-1,n) and find the (m+1)-term recurrence that it satisfies. The matrix form of this recurrence yields a formula

APA, Harvard, Vancouver, ISO, and other styles

12

Li, Ruizhi, Shuli Hu, Shaowei Cai, Jian Gao, Yiyuan Wang, and Minghao Yin. "NuMWVC: A novel local search for minimum weighted vertex cover problem." Journal of the Operational Research Society 71, no. 9 (2019): 1498–509. http://dx.doi.org/10.1080/01605682.2019.1621218.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Tang, Changbing, Ang Li, and Xiang Li. "Asymmetric Game: A Silver Bullet to Weighted Vertex Cover of Networks." IEEE Transactions on Cybernetics 48, no. 10 (2018): 2994–3005. http://dx.doi.org/10.1109/tcyb.2017.2754919.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Pothen, Alex, S. M. Ferdous, and Fredrik Manne. "Approximation algorithms in combinatorial scientific computing." Acta Numerica 28 (May 1, 2019): 541–633. http://dx.doi.org/10.1017/s0962492919000035.

Full text

Abstract:

We survey recent work on approximation algorithms for computing degree-constrained subgraphs in graphs and their applications in combinatorial scientific computing. The problems we consider include maximization versions of cardinality matching, edge-weighted matching, vertex-weighted matching and edge-weighted $b$-matching, and minimization versions of weighted edge cover and $b$-edge cover. Exact algorithms for these problems are impractical for massive graphs with several millions of edges. For each problem we discuss theoretical foundations, the design of several linear or near-linear time

APA, Harvard, Vancouver, ISO, and other styles

15

Chen, Ning, Pinyan Lu, and Hongyang Zhang. "Computing the Nucleolus of Matching, Cover and Clique Games." Proceedings of the AAAI Conference on Artificial Intelligence 26, no. 1 (2021): 1319–25. http://dx.doi.org/10.1609/aaai.v26i1.8242.

Full text

Abstract:

In cooperative games, a key question is to find a division of payoffs to coalition members in a fair manner. Nucleolus is one of such solution concepts that provides a stable solution for the grand coalition. We study the computation of the nucleolus of a number of cooperative games, including fractional matching games and fractional edge cover games on general weighted graphs, as well as vertex cover games and clique games on weighted bipartite graphs. Our results are on the positive side---we give efficient algorithms to compute the nucleolus, as well as the least core, of all of these games

APA, Harvard, Vancouver, ISO, and other styles

16

Qiu, Huaxin, Changhao Sun, Xiaochu Wang, Wei Sun, and Qingrui Zhou. "A population-based game-theoretic optimizer for the minimum weighted vertex cover." Applied Soft Computing 116 (February 2022): 108272. http://dx.doi.org/10.1016/j.asoc.2021.108272.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Li, Ruizhi, Shuli Hu, Haochen Zhang, and Minghao Yin. "An efficient local search framework for the minimum weighted vertex cover problem." Information Sciences 372 (December 2016): 428–45. http://dx.doi.org/10.1016/j.ins.2016.08.053.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Hu, Shuli, Xiaoli Wu, Huan Liu, Yiyuan Wang, Ruizhi Li, and Minghao Yin. "Multi-Objective Neighborhood Search Algorithm Based on Decomposition for Multi-Objective Minimum Weighted Vertex Cover Problem." Sustainability 11, no. 13 (2019): 3634. http://dx.doi.org/10.3390/su11133634.

Full text

Abstract:

The multi-objective minimum weighted vertex cover problem aims to minimize the sum of different single type weights simultaneously. In this paper, we focus on the bi-objective minimum weighted vertex cover and propose a multi-objective algorithm integrating iterated neighborhood search with decomposition technique to solve this problem. Initially, we adopt the decomposition method to divide the multi-objective problem into several scalar optimization sub-problems. Meanwhile, to find more possible optimal solutions, we design a mixed score function according to the problem feature, which is app

APA, Harvard, Vancouver, ISO, and other styles

19

Wang, Deyi, Yuan Quan, and Xiang Li. "A Maximum Degree related Condition to Asymmetric Game in Weighted Vertex Cover Networks." IFAC-PapersOnLine 56, no. 2 (2023): 7394–401. http://dx.doi.org/10.1016/j.ifacol.2023.10.615.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Talmaciu, Mihai, Luminita Dumitriu, Ioan Susnea, Victor Lepin, and Laszlo Barna Iantovics. "Recognition and Optimization Algorithms for P5-Free Graphs." Symmetry 12, no. 2 (2020): 304. https://doi.org/10.3390/sym12020304.

Full text

Abstract:

<em>The weighted independent set problem on P5-free graphs has numerous applications, including data mining and dispatching in railways. The recognition of P5-free graphs is executed in polynomial time. Many problems, such as chromatic number and dominating set, are NP-hard in the class of P5-free graphs. The size of a minimum independent feedback vertex set that belongs to a P5-free graph with n vertices can be computed in O(n16) time. The unweighted problems, clique and clique cover, are NP-complete and the independent set is polynomial. In this work, the P5-free graphs using the weak decomp

APA, Harvard, Vancouver, ISO, and other styles

21

Sun, Changhao, Wei Sun, Xiaochu Wang, and Qingrui Zhou. "Potential Game Theoretic Learning for the Minimal Weighted Vertex Cover in Distributed Networking Systems." IEEE Transactions on Cybernetics 49, no. 5 (2019): 1968–78. http://dx.doi.org/10.1109/tcyb.2018.2817631.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Talmaciu, Mihai, Luminiţa Dumitriu, Ioan Şuşnea, Victor Lepin, and László Barna Iantovics. "Recognition and Optimization Algorithms for P5-Free Graphs." Symmetry 12, no. 2 (2020): 304. http://dx.doi.org/10.3390/sym12020304.

Full text

Abstract:

The weighted independent set problem on P 5 -free graphs has numerous applications, including data mining and dispatching in railways. The recognition of P 5 -free graphs is executed in polynomial time. Many problems, such as chromatic number and dominating set, are NP-hard in the class of P 5 -free graphs. The size of a minimum independent feedback vertex set that belongs to a P 5 -free graph with n vertices can be computed in O ( n 16 ) time. The unweighted problems, clique and clique cover, are NP-complete and the independent set is polynomial. In this work, the P 5 -free graphs using the w

APA, Harvard, Vancouver, ISO, and other styles

23

Pourhassan, Mojgan, Vahid Roostapour, and Frank Neumann. "Runtime analysis of RLS and (1 + 1) EA for the dynamic weighted vertex cover problem." Theoretical Computer Science 832 (September 2020): 20–41. http://dx.doi.org/10.1016/j.tcs.2019.03.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Nguyen, Kien, and Nguyen Hung. "The reverse total weighted distance problem on networks with variable edge lengths." Filomat 35, no. 4 (2021): 1333–42. http://dx.doi.org/10.2298/fil2104333n.

Full text

Abstract:

We address the problem of reducing the edge lengths of a network within a given budget so that the sum of weighted distances from each vertex to others is minimized. We call this problem the reverse total weighted distance problem on networks. We first show that the problem is NP-hard by reducing the set cover problem to it in polynomial time. Particularly, we develop a linear time algorithm to solve the problem on a tree. For the problem on cycles, we devise an iterative approach without mentioning the exact complexity. Additionally, if the cycle has uniform edge lengths, we can prove that th

APA, Harvard, Vancouver, ISO, and other styles

25

Fan, Lidan, Zhao Zhang, and Wei Wang. "PTAS for minimum weighted connected vertex cover problem with c-local condition in unit disk graphs." Journal of Combinatorial Optimization 22, no. 4 (2010): 663–73. http://dx.doi.org/10.1007/s10878-010-9315-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Li, Guang-Hui, Sha-Sha Wang, Xiao-Hui Ni, et al. "Performance analysis of the quantum alternating operator ansatz for solving the minimum weighted vertex cover problem." Physics Letters A 553 (September 2025): 130690. https://doi.org/10.1016/j.physleta.2025.130690.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Klemz, Boris, and Günter Rote. "Linear-Time Algorithms for Maximum-Weight Induced Matchings and Minimum Chain Covers in Convex Bipartite Graphs." Algorithmica 84, no. 4 (2022): 1064–80. http://dx.doi.org/10.1007/s00453-021-00904-w.

Full text

Abstract:

AbstractA bipartite graph $$G=(U,V,E)$$ G = ( U , V , E ) is convex if the vertices in V can be linearly ordered such that for each vertex $$u\in U$$ u ∈ U , the neighbors of u are consecutive in the ordering of V. An induced matchingH of G is a matching for which no edge of E connects endpoints of two different edges of H. We show that in a convex bipartite graph with n vertices and mweighted edges, an induced matching of maximum total weight can be computed in $$O(n+m)$$ O ( n + m ) time. An unweighted convex bipartite graph has a representation of size O(n) that records for each vertex $$u\

APA, Harvard, Vancouver, ISO, and other styles

28

Samosir, Mega Agustina, and Mulyono. "Application of the Dijkstra and Floyd – Warshall Algorithms in Determining the Shortest Route to Tourist Attractions in Toba." Formosa Journal of Science and Technology 2, no. 2 (2023): 453–74. http://dx.doi.org/10.55927/fjst.v2i2.2858.

Full text

Abstract:

The Toba Regency Government focuses on developing the tourism sector, because the natural resources in Toba Regency have great potential. The purpose of this research is to determine the shortest route to an effective tourist spot and the time it takes to cover that distance. The method used to determine the shortest route is the Dijkstra and Floyd - Warshall Algorithms. Dijkstra's algorithm aims to choose the best solution from each set of solutions, while the Floyd-Warshall algorithm compares all possible paths on the graph for each vertex. Based on the research results, the shortest route f

APA, Harvard, Vancouver, ISO, and other styles

29

Marx, Dániel, and Michał Pilipczuk. "Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams." ACM Transactions on Algorithms 18, no. 2 (2022): 1–64. http://dx.doi.org/10.1145/3483425.

Full text

Abstract:

We study a general family of facility location problems defined on planar graphs and on the two-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the n O (√ k ) time brute force algorithm of selecting k objects can be improved to n O (√ k ) time. The algorithm is based on an idea that was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. We focus on the Voronoi diagram

APA, Harvard, Vancouver, ISO, and other styles

30

Dagdeviren, Zuleyha Akusta. "Weighted Connected Vertex Cover Based Energy-Efficient Link Monitoring for Wireless Sensor Networks Towards Secure Internet of Things." IEEE Access 9 (2021): 10107–19. http://dx.doi.org/10.1109/access.2021.3050930.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Wang, Limin, Wenxue Du, Zhao Zhang, and Xiaoyan Zhang. "A PTAS for minimum weighted connected vertex cover $$P_3$$ P 3 problem in 3-dimensional wireless sensor networks." Journal of Combinatorial Optimization 33, no. 1 (2015): 106–22. http://dx.doi.org/10.1007/s10878-015-9937-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Pastravanu, Octavian, and Mihaela-Hanako Matcovschi. "Stability of Matrix Polytopes with a Dominant Vertex and Implications for System Dynamics." Abstract and Applied Analysis 2013 (2013): 1–11. http://dx.doi.org/10.1155/2013/396759.

Full text

Abstract:

The paper considers the class of matrix polytopes with a dominant vertex and the class of uncertain dynamical systems defined in discrete time and continuous time, respectively, by such polytopes. We analyze the standard concept of stability in the sense of Schur—abbreviated as SS (resp., Hurwitz—abbreviated as HS), and we develop a general framework for the investigation of the diagonal stability relative to an arbitrary Hölderp-norm,1≤p≤∞, abbreviated asSDSp(resp.,HDSp). Our framework incorporates, as the particular case withp=2, the known condition of quadratic stability satisfied by a diag

APA, Harvard, Vancouver, ISO, and other styles

33

Mkrtchyana, Vahan, and Garik Petrosyan. "On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs." Journal of Graph Algorithms and Applications 26, no. 1 (2022): 91–110. http://dx.doi.org/10.7155/jgaa.00584.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Wu, Jun, and Minghao Yin. "A Restart Local Search for Solving Diversified Top-k Weight Clique Search Problem." Mathematics 9, no. 21 (2021): 2674. http://dx.doi.org/10.3390/math9212674.

Full text

Abstract:

Diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with practical applications. The diversified top-k weight clique search problem aims to search k maximal cliques that can cover the maximum weight in a vertex weighted graph. In this work, we propose a novel local search algorithm called TOPKWCLQ for the DTKWC search problem which mainly includes two strategies. First, a restart strategy is adopted, which repeated the construction and updating processes of the maximal weight clique set. Second, a scoring h

APA, Harvard, Vancouver, ISO, and other styles

35

Ren, Xiao-Long, Niels Gleinig, Dirk Helbing, and Nino Antulov-Fantulin. "Generalized network dismantling." Proceedings of the National Academy of Sciences 116, no. 14 (2019): 6554–59. http://dx.doi.org/10.1073/pnas.1806108116.

Full text

Abstract:

Finding an optimal subset of nodes in a network that is able to efficiently disrupt the functioning of a corrupt or criminal organization or contain an epidemic or the spread of misinformation is a highly relevant problem of network science. In this paper, we address the generalized network-dismantling problem, which aims at finding a set of nodes whose removal from the network results in the fragmentation of the network into subcritical network components at minimal overall cost. Compared with previous formulations, we allow the costs of node removals to take arbitrary nonnegative real values

APA, Harvard, Vancouver, ISO, and other styles

36

Tian, Lijia, Xingjian Ji, and Yupeng Zhou. "Maximizing Information Dissemination in Social Network via a Fast Local Search." Systems 13, no. 1 (2025): 59. https://doi.org/10.3390/systems13010059.

Full text

Abstract:

In recent years, social networks have become increasingly popular as platforms for personal expression, commercial transactions, and government management. The way information propagates on these networks influences the quality and expenses of social network activities, garnering substantial interest. This study addresses the enhancement of information spread in large-scale social networks constrained by resources, by framing the issue as a unique weighted k-vertex cover problem. To tackle this complex NP-hard optimization problem, a rapid local search algorithm named FastIM is introduced. A f

APA, Harvard, Vancouver, ISO, and other styles

37

Nazarevych, Valerii, Artem Mykytiuk, Olha Shevchuk, and Ihor Kulyk. "A method of secure network traffic routing based on specified criterias." Collection "Information Technology and Security" 11, no. 2 (2023): 156–65. http://dx.doi.org/10.20535/2411-1031.2023.11.2.293752.

Full text

Abstract:

Due to the implementation of new network services, the increase amount of data that need to be transmitted, and the use of networks in various sectors with diverse communication requirements, there is a need to develop new approaches to ensure the quality of such communications. Leading network equipment manufacturers and standardization organizations are developing new routing algorithms, resulting in the introduction of new routing protocols or improvements to existing ones. However, all these algorithms cover routing principles for general-purpose networks and do not consider the communicat

APA, Harvard, Vancouver, ISO, and other styles

38

Mandal, Mousumi, and Dipak Kumar Pradhan. "Symbolic powers in weighted oriented graphs." International Journal of Algebra and Computation 31, no. 03 (2021): 533–49. http://dx.doi.org/10.1142/s0218196721500260.

Full text

Abstract:

Let [Formula: see text] be a weighted oriented graph with the underlying graph [Formula: see text] when vertices with non-trivial weights are sinks and [Formula: see text] be the edge ideals corresponding to [Formula: see text] and [Formula: see text] respectively. We give an explicit description of the symbolic powers of [Formula: see text] using the concept of strong vertex covers. We show that the ordinary and symbolic powers of [Formula: see text] and [Formula: see text] behave in a similar way. We provide a description for symbolic powers and Waldschmidt constant of [Formula: see text] fo

APA, Harvard, Vancouver, ISO, and other styles

39

PAULSEN, CHELSEY, and SEAN SATHER-WAGSTAFF. "EDGE IDEALS OF WEIGHTED GRAPHS." Journal of Algebra and Its Applications 12, no. 05 (2013): 1250223. http://dx.doi.org/10.1142/s0219498812502234.

Full text

Abstract:

We study weighted graphs and their "edge ideals" which are ideals in polynomial rings that are defined in terms of the graphs. We provide combinatorial descriptions of m-irreducible decompositions for the edge ideal of a weighted graph in terms of the combinatorics of "weighted vertex covers". We use these, for instance, to say when these ideals are m-unmixed. We explicitly describe which weighted cycles, suspensions, and trees are unmixed and which ones are Cohen–Macaulay, and we prove that all weighted complete graphs are Cohen–Macaulay.

APA, Harvard, Vancouver, ISO, and other styles

40

Pullan, Wayne. "Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers." Discrete Optimization 6, no. 2 (2009): 214–19. http://dx.doi.org/10.1016/j.disopt.2008.12.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

LE GALL, A., and V. ZISSIMOPOULOS. "A COMPETITIVE ACTIVATION NEURAL NETWORK MODEL FOR THE WEIGHTED MINIMUM VERTEX COVERING." International Journal of Neural Systems 07, no. 05 (1996): 607–16. http://dx.doi.org/10.1142/s0129065796000592.

Full text

Abstract:

We give a generalization of a neural network model originally developed to solve the minimum cardinality vertex covering problem, in order to solve the weighted version of the problem. The model is governed by a modified activation rule and we show that it has some important properties, namely convergence and irredundant covers at stable states. We present experimental results that confirm the effectiveness of the model.

APA, Harvard, Vancouver, ISO, and other styles

42

Bentz, C., M. C. Costa, C. Picouleau, B. Ries, and D. de Werra. "d-Transversals of stable sets and vertex covers in weighted bipartite graphs." Journal of Discrete Algorithms 17 (December 2012): 95–102. http://dx.doi.org/10.1016/j.jda.2012.06.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Khuller, S., U. Vishkin, and N. Young. "A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers." Journal of Algorithms 17, no. 2 (1994): 280–89. http://dx.doi.org/10.1006/jagm.1994.1036.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

BALOGH, JOZSEF, GRAEME KEMKES, CHOONGBUM LEE, and STEPHEN J. YOUNG. "Towards a Weighted Version of the Hajnal–Szemerédi Theorem." Combinatorics, Probability and Computing 22, no. 3 (2013): 346–50. http://dx.doi.org/10.1017/s0963548313000059.

Full text

Abstract:

For a positive integer r ≥ 2, a Kr-factor of a graph is a collection vertex-disjoint copies of Kr which covers all the vertices of the given graph. The celebrated theorem of Hajnal and Szemerédi asserts that every graph on n vertices with minimum degree at least $(1-\frac{1}{r})n contains a Kr-factor. In this note, we propose investigating the relation between minimum degree and existence of perfect Kr-packing for edge-weighted graphs. The main question we study is the following. Suppose that a positive integer r ≥ 2 and a real t ∈ [0, 1] is given. What is the minimum weighted degree of Kn tha

APA, Harvard, Vancouver, ISO, and other styles

45

S., Balaji, Swaminathan V., and Kannan K. "An Effective Algorithm for Minimum Weighted Vertex Cover Problem." July 25, 2010. https://doi.org/10.5281/zenodo.1076814.

Full text

Abstract:

The Minimum Weighted Vertex Cover (MWVC) problem is a classic graph optimization NP - complete problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the minimum weighted vertex cover problem is to find a vertex set S V whose total weight is minimum subject to every edge of G has at least one end point in S. In this paper an effective algorithm, called Support Ratio Algorithm (SRA), is designed to find the minimum weighted vertex cover of a graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Ex

APA, Harvard, Vancouver, ISO, and other styles

46

Mandal, Soumen, Pranabendu Misra, Ashutosh Rai, and Saket Saurabh. "Parameterized Approximation Algorithms for Weighted Vertex Cover." Theoretical Computer Science, September 2024, 114870. http://dx.doi.org/10.1016/j.tcs.2024.114870.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Polyanskii, Alexander, and Rynat Sadykov. "Alon–Boppana-Type Bounds for Weighted Graphs." Electronic Journal of Combinatorics 31, no. 1 (2024). http://dx.doi.org/10.37236/12212.

Full text

Abstract:

The unraveled ball of radius $r$ centered at a vertex $v$ in a weighted graph $G$ is the ball of radius $r$ centered at $v$ in the universal cover of $G$. We present a general bound on the maximum spectral radius of unraveled balls of fixed radius in a weighted graph. The weighted degree of a vertex in a weighted graph is the sum of weights of edges incident to the vertex. A weighted graph is called regular if the weighted degrees of its vertices are the same. Using the result on unraveled balls, we prove a variation of the Alon–Boppana theorem for regular weighted graphs.

APA, Harvard, Vancouver, ISO, and other styles

48

S., Balaji, Swaminathan V., and Kannan K. "Approximating Maximum Weighted Independent Set Using Vertex Support." November 26, 2009. https://doi.org/10.5281/zenodo.1078659.

Full text

Abstract:

The Maximum Weighted Independent Set (MWIS) problem is a classic graph optimization NP-hard problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the MWIS problem is to find a vertex set S V whose total weight is maximum subject to no two vertices in S are adjacent. This paper presents a novel approach to approximate the MWIS of a graph using minimum weighted vertex cover of the graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the proposed algorithm ca

APA, Harvard, Vancouver, ISO, and other styles

49

Li, Ruizhi, Shaowei Cai, Shuli Hu, Minghao Yin, and Jian Gao. "NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem." Proceedings of the AAAI Conference on Artificial Intelligence 32, no. 1 (2018). http://dx.doi.org/10.1609/aaai.v32i1.12137.

Full text

Abstract:

The minimum weighted vertex cover (MWVC) problem is a well known combinatorial optimization problem with important applications. This paper introduces a novel local search algorithm called NuMWVC for MWVC based on three ideas. First, four reduction rules are introduced during the initial construction phase. Second, the configuration checking with aspiration is proposed to reduce cycling problem. Moreover, a self-adaptive vertex removing strategy is proposed to save time.

APA, Harvard, Vancouver, ISO, and other styles

50

Mkrtchyan, Vahan, Ojas Parekh, and K. Subramani. "Approximation Algorithms for Partial Vertex Covers in Trees." International Journal of Foundations of Computer Science, June 28, 2023, 1–21. http://dx.doi.org/10.1142/s0129054123500089.

Full text

Abstract:

This paper is concerned with designing algorithms for and analyzing the computational complexity of the partial vertex cover problem in trees. Graphs (and trees) are frequently used to model risk management in various systems. In particular, Caskurlu et al. in [4] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. In this paper, we focu

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!