Name
Abstract | ||
|---|---|---|
Some algorithms and statistics of the vertex-cover solution space on bipartite graphs are investigated in this paper. Based on Konig's theorem, an exact algorithm for solution space expression is proposed and some statistical analysis of the nodes' states is provided. The statistical results fit well with the algorithmic ones before the emergence of the unfrozen core, which leads to fluctuations of the statistical quantities and produces replica symmetric breaking in the solutions. Besides, the entropy and the clustering entropy of bipartite-graph vertex-cover solutions are calculated using some cycle simplification technique for the unfrozen core. Furthermore, as a generalization of bipartite graphs, a bipartite core graph is proposed, the solution space of which can also be easily determined; and to have further knowledge on the easily-solving vertex-cover instances, how to generate a Konig-Egervary subgraph is studied by a growth process of adding edges. The investigation on the solution space of a bipartite-graph vertex-cover provides some insights and intensive understanding on solution space complexity, and will provide benefits in finding the maximum Konig-Egervary subgraphs, solving a general-graph vertex-cover and recognizing the intrinsic hardness of NP-complete problems. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1088/1742-5468/2015/11/P11027 | JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT |
Keywords | Field | DocType |
disordered systems (theory),classical phase transitions (theory),phase diagrams (theory),cavity and replica method | Discrete mathematics,Graph,Replica,Combinatorics,Exact algorithm,Bipartite graph,Vertex cover,Cluster analysis,Blossom algorithm,Mathematics,Statistical analysis | Journal |
Volume | Issue | ISSN |
abs/1505.06955 | 11 | 1742-5468 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wei Wei | 1 | 0 | 1.35 |
| yunjia zhang | 2 | 0 | 0.34 |
| Wang Ting | 3 | 55 | 14.14 |
| baifeng li | 4 | 0 | 0.34 |
| baolong niu | 5 | 0 | 0.34 |
| Zhiming Zheng | 6 | 128 | 16.80 |