An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u...An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.展开更多
As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer science in recent years. Due to the difficulty in the research on computa- tional complexi...As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer science in recent years. Due to the difficulty in the research on computa- tional complexity of the backbone, many researchers analyzed the backbone by statistic ways. Aiming to increase the backbone size which is usually very small by the existing methods, the unique optimal solution instance construction (UOSIC) is proposed for the graph bi-partitioning problem (GBP). Also, we prove by using the UOSIC that it is NP-hard to obtain the backbone, i.e. no algorithm exists to obtain the backbone of a GBP in polynomial time under the assumption that P ≠ NP. Our work expands the research area of computational complexity of the backbone. And the UOSIC provides a new way for heuristic design of NP-hard problems.展开更多
基金The NSF (60673048) of China the NSF (KJ2009B002,KJ2009B237Z) of Education Ministry of Anhui Province.
文摘An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.
基金Supported by the National Natural Science Foundation of China (Grant Nos. 60673046 and 60673066)the Natural Science Foundation of Liaoning Province (Grant No. 20051082)the Gifted Young Foundation of Dalian University of Technology
文摘As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer science in recent years. Due to the difficulty in the research on computa- tional complexity of the backbone, many researchers analyzed the backbone by statistic ways. Aiming to increase the backbone size which is usually very small by the existing methods, the unique optimal solution instance construction (UOSIC) is proposed for the graph bi-partitioning problem (GBP). Also, we prove by using the UOSIC that it is NP-hard to obtain the backbone, i.e. no algorithm exists to obtain the backbone of a GBP in polynomial time under the assumption that P ≠ NP. Our work expands the research area of computational complexity of the backbone. And the UOSIC provides a new way for heuristic design of NP-hard problems.
