Research of the Minimum Vertex-Cover Solutions on the Tree and Lattice Structures

Yun Jia Zhang; Wei  Wei; Ting Wang

doi:10.4028/www.scientific.net/AMR.989-994.4926

Paper Titles

Internet Public Opinion Recognition and Tracking Based on Web Mining
p.4909

Data Redundancy Replication Strategy Based on Relevant Failure in Cloud Environment
p.4913

Research and Implementation of Oracle Database Synchronization Timing
p.4917

User Behavior Prediction Analysis Based on Time Context
p.4920

Research of the Minimum Vertex-Cover Solutions on the Tree and Lattice Structures
p.4926

Research on Multi-Channel Network Information Interactive Technology
p.4930

Collective Communication Optimization for Solving Linear Algebraic Equations
p.4934

Trusted Software Architecture Evolution Based on Graph Transformation Rule
p.4940

The Method Research of Environmental Noise 3D Graphic Expression Based on CityEngine
p.4945

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 989-994Research of the Minimum Vertex-Cover Solutions on...

Research of the Minimum Vertex-Cover Solutions on the Tree and Lattice Structures

Abstract:

We focus the solution space of a most fundamental problem - Minimum Vertex-Cover problem - in theoretical computer science. After some rigorous analysis, we provide the formation mechanism of minimum vertex-cover solutions on the tree and give the organization of these solutions on arbitrary lattice structure. By the results, we can easily calculate the solution numbers on these structures and have better understanding of the hardness of Minimum Vertex-Cover problem. The proposed study and algorithm can make a new way on detecting the essential difficulty of NP-complete problems and designing efficient algorithms on solving them.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 989-994)

Pages:

4926-4929

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.989-994.4926

Citation:

Cite this paper

Online since:

July 2014

Authors:

Yun Jia Zhang*, Wei Wei, Ting Wang

Keywords:

Computational Complexity, Minimum Vertex-Cover Problem, Solution Space Organization

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] R.M. Karp, in Proc. Sympos. IBM Thomas J. Watson Res. Center (Plenum, New York, 1972), p.85–103.

Google Scholar

[2] J. Gomez-Gardenes, P. Echenique, and Y. Moreno, Eur. Phys. J. B 49, 259 (2006).

Google Scholar

[3] Y. Breitbart, C. Y. Chan, M. Garofalakis, R. Rastogi, and A. Silverschatz, in Proc. IEEE INFOCOM (IEEE Communication Society, Anchorage, Alaska, 2001), p.933–942.

Google Scholar

[4] P. Kilby, J. Slaney, S. Thiebaux, and T. Walsh, in Proc. of the 20th Ntl. Conf. on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conf. (AAAI/MIT Press, Menlo Park, 2005).

Google Scholar

[5] W. Wei, R. Zhang, B. Guo, and Z. Zheng, Phys. Rev. E 86, 016112 (2012).

Google Scholar

[6] A. Braunstein, M. Mezard, and R. Zecchina, Random. Struct. Algor. 27(2), 201 (2005).

Google Scholar

[7] L.G. Valiant, Theor. Comp. Sci. 8(2) (1979) 189-201.

Google Scholar

[8] M. Weigt and A. K. Hartmann, Phys. Rev. Lett. 84, 6118 (2000).

Google Scholar

[9] M. Bauer and O. Golinelli, Eur. Phys. J. B 24, 339 (2001).

Google Scholar

[10] B. Bollobas, Random Graphs (Academic Press, New York, 1985).

Google Scholar

[11] A. Vazquez1 and M. Weigt, Phys. Rev. E 67 , 027101 (2003).

Google Scholar