Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: J Comput Sci Technol

Search In Journal Title:

Abbravation: Journal of Computer Science and Technology

Search In Journal Abbravation:

Publisher

Springer US

Search In Publisher:

DOI

10.1016/1058-9139(92)90012-2

Search In DOI:

ISSN

1860-4749

Search In ISSN:
Search In Title Of Papers:

Approximation Algorithm Based on Chain Implication

Authors: JianXin Wang XiaoShuang Xu JianEr Chen
Publish Date: 2008/11/03
Volume: 23, Issue: 5, Pages: 763-768
PDF Link

Abstract

The constrained minimum vertex cover problem on bipartite graphs the MinCVCB problem is an important NPcomplete problem This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication For any given constant ɛ  0 if an instance of the MinCVCB problem has a minimum vertex cover of size k u k l our algorithm constructs a vertex cover of size k u k l satisfying max k u /k u k l /k l  ≤ 1 + ɛThis work is supported by the National Natural Science Foundation of China under Grant Nos 60433020 and 60773111 the National Basic Research 973 Program of China under Grant No 2008CB317107 the Provincial Natural Science Foundation of Hunan under Grant No 06JJ10009 the Program for New Century Excellent Talents in University under Grant No NCET050683 and the Program for Changjiang Scholars and Innovative Research Team in University under Grant No IRT0661

Keywords:

References

.
Search In Abstract Of Papers:
Other Papers In This Journal:
  1. Review Authorship Attribution in a Similarity Space
  2. A Distributed Mechanism for Handling of Adaptive/Intelligent Selfish Misbehaviour at MAC Layer in Mobile Ad Hoc Networks
  3. View-Aware Image Object Compositing and Synthesis from Multiple Sources
  4. Continuous Outlier Monitoring on Uncertain Data Streams
  5. ROPAS: Cross-Layer Cognitive Architecture for Mobile UWB Networks
  6. Stroke Style Analysis for Painterly Rendering
  7. Dominant Skyline Query Processing over Multiple Time Series
  8. Optimal Feature Extraction Using Greedy Approach for Random Image Components and Subspace Approach in Face Recognition
  9. Multilevel Threshold Based Image Denoising in Curvelet Domain
  10. A Heuristic Clustering Algorithm for Mining Communities in Signed Networks
  11. Design-Rule-Aware Congestion Model with Explicit Modeling of Vias and Local Pin Access Paths
  12. A Parallel Interval Computation Model for Global Optimization with Automatic Load Balancing
  13. An Abstract Reachability Approach by Combining HOL Induction and Multiway Decision Graphs
  14. t -Private and t -Secure Auctions
  15. GPP-Based Soft Base Station Designing and Optimization
  16. On Unsupervised Training of Multi-Class Regularized Least-Squares Classifiers
  17. Combined Cloud: A Mixture of Voluntary Cloud and Reserved Instance Marketplace
  18. A Rigorous Architectural Approach to Adaptive Software Engineering
  19. Computational Cellular Dynamics Based on the Chemical Master Equation: A Challenge for Understanding Complexity
Search Result: