An Approximation Algorithm for Minimum Vertex Cover on General Graphs

Shaohua Li; Jianxin Wang; Jianer Chen; Zhijian Wang
June 2010
Proceedings of the International Symposium on Electronic Commerc;Jun2010, p249
Conference Proceeding
Minimum vertex cover problem on a general graph is a NP-hard problem. The neighborhood relationship of a vertex plays a special role in Min-VC solving process. A concept of Max-I share degree is proposed in this paper, and a heuristic algorithm based on Max-I share degree is designed. Theory and experiment show that our algorithm can get almost the same result with the exact algorithm, Significantly better than other main heuristic methods in current.


Related Articles

  • Algorithms for the Bin Packing Problem with Conflicts. Fernandes Muritiba, Albert E.; Iori, Manuel; Malaguti, Enrico; Toth, Paolo // INFORMS Journal on Computing;Summer2010, Vol. 22 Issue 3, p401 

    We consider a particular bin packing problem in which some pairs of items may be in conflict and cannot be assigned to the same bin. The problem, denoted as the bin packing problem with conflicts, is of practical and theoretical interest because of its many real-world applications and because it...

  • The Effect of the First Cue Outcome on the Use of One-Reason Heuristics. Dong-gook Kim; Whalen, Thomas // International Journal of Business & Social Science;2012, Vol. 3 Issue 7, p46 

    One-reason heuristics are decision methods relying on only one good piece of information or one cue. In the past empirical studies of these heuristics, many participants used non-one-reason heuristics in spite of experimental conditions that called for the use of one-reason heuristics. In this...

  • A HYBRID TEST OPTIMIZATION FRAMEWORK -- COUPLING GENETIC ALGORITHM WITH LOCAL SEARCH TECHNIQUE. MALA, Dharmalingam JEYA; RUBY, Elizabeth; MOHAN, Vasudev // Computing & Informatics;2010, Vol. 29 Issue 1, p133 

    Quality of test cases is determined by their ability to uncover as many errors as possible in the software code. In our approach, we applied Hybrid Genetic Algorithm (HGA) for improving the quality of test cases. This improvement can be achieved by analyzing both mutation score and path coverage...

  • QoS Guided Heuristic Algorithms for Grid Task Scheduling.  // International Journal of Computer Applications;Mar2010, Vol. 2, p24 

    The article presents a study on heuristic algorithms for grid task scheduling which is based on quality of service (QoS). It discusses QoS Guided Weighted Mean Time-min and QoS Guided Weighted Mean Time Min-Min Max Min Selective algorithms which were simulated using GridSim. It details the...

  • Heuristic algorithms for effective broker deployment. Yifeng Qian; Beihong Jin; Wenjing Fang // Information Technology & Management;Jun2011, Vol. 12 Issue 2, p55 

    In the pervasive e-business applications covering large geographical areas and involving many RFID readers or sensors, broker deployment strategies have a direct effect on the deployment cost and collaboration efficiency. By analyzing the deployment cost and collaboration basis, this paper...

  • TOPSIL-Miner: an efficient algorithm for mining top- K significant itemsets over data streams. Yang, Bei; Huang, Houkuan // Knowledge & Information Systems;May2010, Vol. 23 Issue 2, p225 

    Frequent itemset mining over data streams becomes a hot topic in data mining and knowledge discovery in recent years, and has been applied to different areas. However, the setting of a minimum support threshold needs some domain knowledge. It will bring a lot of difficulties or much burden to...

  • Cycle transversals in bounded degree graphs. Groshaus, Marina; Hell, Pavol; Klein, Sulamita; Nogueira, Loana Tito; Protti, F�bio // Discrete Mathematics & Theoretical Computer Science (DMTCS);Jan2011, Vol. 13 Issue 1, p45 

    In this work we investigate the algorithmic complexity of computing a minimum Ck-transversal, i.e., a subset of vertices that intersects all the chordless cycles with k vertices of the input graph, for a fixed k = 3. For graphs of maximum degree at most three, we prove that this problem is...

  • LP-based approximation algorithms for capacitated facility location. Levi, Retsef; Shmoys, David; Swamy, Chaitanya // Mathematical Programming;Feb2012, Vol. 131 Issue 1/2, p365 

    In the capacitated facility location problem with hard capacities, we are given a set of facilities, $${\mathcal{F}}$$, and a set of clients $${\mathcal{D}}$$ in a common metric space. Each facility i has a facility opening cost f and capacity u that specifies the maximum number of clients that...

  • Interval scheduling and colorful independent sets. Bevern, René; Mnich, Matthias; Niedermeier, Rolf; Weller, Mathias // Journal of Scheduling;Oct2015, Vol. 18 Issue 5, p449 

    Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer $$k$$ , find a set of at least $$k$$ pairwise non-adjacent vertices). Here, one encounters special graph...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics