Tabu Search를 이용한 지름이 2인 그래프에 대한 L(2,1)-coloring 문제 해결
Using Tabu Search for L(2,1)-coloring Problem of Graphs with Diameter 2
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
단순 무방향 그래프 의 L(2,1)-coloring은 가 두 정점 사이의 거리일 때 두 가지 조건 (1) 라면 , (2) 라면 을 만족하는 함수 를 정의하는 것이다. 임의의 L(2,1)-coloring 에 대하여 의 -span 은 이며, L(2,1)-coloring number 인 는 모든 가능한 에 대하여 로 정의된다. 본 논문에서는 Harary의 정리에 기반하여 지름이 2인 그래프에 대하여 여그래프에 해밀턴 경로의 존재여부를 Tabu Search를 사용해 판단하고 이를 통해 가 과 같음을 분석한다.
Abstract
For simple undirected graph , L(2,1)-coloring of is a nonnegative real-valued function such that whenever vertices and are adjacent in then and whenever the distance between and is 2, . For a given L(2,1)-coloring of graph , the -span is . L(2,1)-coloring number where the minimum is taken over all L(2,1)-coloring of graph . In this paper, based on Harary’s Theorem, we use Tabu Search to figure out the existence of Hamiltonian Path in a complementary graph and confirmed that if is equal to .
참고문헌 (19)
- J. R. Griggs, "Labelling graphs with a condition at distance 2", SIAM Journal on Discrete Mathematics, 5(4), pp.586~595 (1992)
- F. Harary, "Graphs Whose Radio Coloring Number Equals the Number", Graph Colouring and Applications, 23(23) (1999)
- K. I. Aardal, "Models and solution techniques for frequency assignment problems", Annals of Operations Research, 153(1), pp.79~129 (2007)
- L. Liwei, "Simulated annealing algorithm in solving frequency assignment problem", 2010 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE), 1, pp.V1~361 (2010), IEEE
- V. Maniezzo, "An ANTS heuristic for the frequency assignment problem", Future Generation Computer Systems, 16(8), pp.927~935 (2000)
- T. Park, "Application of the graph coloring algorithm to the frequency assignment problem", Journal of the Operations Research society of Japan, 39(2), pp.258~265 (1996)
- M. Alabau, "New hybrid genetic algorithms for the frequency assignment problem", IEEE Transactions on Broadcasting, 48(1), pp.27~34 (2002)
- J. K. Hao, "European Conference on Artificial Evolution", pp.333~344 (1995), Springer
- S. Vollala, "Implementation of algorithms for L (2, 1)-coloring problems", 2017 8th International Conference on Computing, Communication and Networking Technologies (ICCCNT), pp.1~6 (2017), IEEE
- S. Paul, "L(2, 1)-labeling of interval graphs", Journal of Applied Mathematics and Computing, 49(1), pp.419~432 (2015)
- M. R. Cerioli, "On L(2, 1)-coloring split, chordal bipartite, and weakly chordal graphs", Discrete Applied Mathematics, 160(18), pp.2655~2661 (2012)
- G. J. Chang, "The L(2,1)-labeling problem on graphs", SIAM Journal on Discrete Mathematics, 9(2), pp.309~316 (1996)
- F. W. Glover, "Tabu Search" (1998), Springer Science & Business Media
- E. K. Burke, "Search methodologies: introductory tutorials in optimization and decision support techniques" (2014), Springer
- F. Glover, "Heuristics for Integer programming using surrogate constraints", Decision Sciences, 8(1), pp.156~166 (1977)
- K. I. Aardal, "A branch-and-cut algorithm for the frequency assignment problem", Research Memorandum, 96(011), pp.3~7 (1996)
- H. L. Bodlaender, "Approximations for λ-colorings of graphs", The Computer Journal, 47(2), pp.193~204 (2004)
- D. H. Smith, "Improving heuristics for the frequency assignment problem", European Journal of Operational Research, 107(1), pp.76~86 (1998)
- W. K. Hale, "Frequency assignment: Theory and applications", Proceedings of the IEEE, 68(12), pp.1497~1514 (1980)