Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán xấp xỉ $$\frac{5}{2}$$ cho việc tô màu các cây con có gốc của cây bậc 3
Tóm tắt
Một cây có gốc $$\mathbf {R}$$ là một cây con có gốc của cây T nếu cây thu được bằng cách thay thế các cạnh có hướng của $$\mathbf {R}$$ bằng các cạnh không hướng là một cây con của T. Chúng tôi nghiên cứu bài toán gán màu tối thiểu cho một tập hợp các cây con có gốc $${\mathcal {R}}$$ của một cây T cho trước sao cho nếu hai cây con có gốc chia sẻ một cạnh có hướng, thì chúng phải được gán các màu khác nhau. Bài toán này là NP khó ngay cả trong trường hợp khi bậc của T bị giới hạn ở tối đa là 3 (Erlebach và Jansen, trong: Tài liệu Hội nghị Quốc tế về khoa học hệ thống Hawaii lần thứ 30, trang 221, 1997). Chúng tôi trình bày một thuật toán xấp xỉ $$\frac{5}{2}$$ cho bài toán này. Động lực để nghiên cứu bài toán này xuất phát từ bài toán gán các bước sóng cho các yêu cầu lưu lượng đa phát trong các mạng cây WDM quang hoàn toàn.
Từ khóa
#cây con có gốc #thuật toán xấp xỉ #tô màu #cây bậc 3 #WDM quang hoàn toànTài liệu tham khảo
Ali M, Deogun JS (2000) Cost-effective implementation of multicasting in wavelength-routed networks. IEEE/OSA J Lightwave Technol 18(12):1628–1638
Auletta V, Caragiannis I, Kaklamanis C, Persiano P (2000) Randomized path coloring on binary trees. In: Proceedings of the 3rd international workshop on approximation algorithms for combinatorial optimization problems, LNCS, vol 1913, pp 407–421. Springer, Berlin
Bollobas B (1998) Modern graph theory. Springer, Berlin
Caragiannis I, Kaklamanis C, Persiano P (1997) Bounds on optical bandwidth allocation in directed fiber tree technologies. In: 2nd workshop on optics and computer science
Caragiannis I, Kaklamanis C, Persiano P (2001) Wavelength routing in all-optical tree networks: a survey. Comput Inform (Former Comput Artif Intell) 20(2):95–120
Caragiannis I, Kaklamanis C, Persiano P (2004) Approximate path coloring with applications to wavelength assignment in WDM optical networks. In: Proceedings of the 21st international symposium on theoretical aspects of computer science, LNCS, vol 2996, pp 258–269. Springer, Berlin
Caragiannis I, Kaklamanis C, Persiano P (2006) Approximation algorithms for path coloring in trees. LNCS, vol 3484. Springer, Berlin, pp 74–96
Erlebach T, Jansen K (1996) Scheduling of virtual connections in fast networks. In: Proceedings of the 4th parallel systems and algorithms workshop
Erlebach T, Jansen K (1997) Call scheduling in trees, rings and meshes. In: Proceedings of the 30th Hawaii international conference on system sciences, p 221
Erlebach T, Jansen K (2001) The complexity of path coloring and call scheduling. Theoret Comput Sci 255(1–2):33–50
Fulkerson DR, Gross OA (1965) Incidence matrices and interval graphs. Pac J Math 15(3):835–855
Gavril F (1972) Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J Comput 1(2):180–187
Golumbic MC, Lipshteyn M, Stern M (1985) The edge intersection graphs of paths in a tree. J Comb Theory Ser B 38(1):8–22
Golumbic MC, Lipshteyn M, Stern M (2005) Representations of edge intersection graphs of paths in a tree. In: Proceedings of the European conference on combinatorics, graph theory and applications, discrete mathematics and theoretical computer science, pp 87–92
Golumbic MC, Lipshteyn M, Stern M (2006) Finding intersection models of weakly chordal graphs. In: Proceedings of the 32nd international workshop on graph-theoretic concepts in computer science, LNCS, vol 4271, pp 241–255. Springer, Berlin
Hayward RB (1985) Weakly triangulated graphs. J Comb Theory Ser B 39(3):200–208
Hayward RB, Spinrad JP, Sritharan R (2007) Improved algorithms for weakly chordal graphs. ACM Trans Algorithms 3(2):14-es
Holyer I (1981) The np-completeness of edge-coloring. SIAM J Comput 10(4):718–720
Jamison RE, Mulder HM (2005) Constant tolerance intersection graphs of subtrees of a tree. Discrete Math 290(1):27–46
Jansen K (1997) Approximation results for wavelength routing in directed binary trees. In: 2nd Workshop on optics and computer science
Kaklamanis C, Persiano G (1996) Efficient wavelength routing on directed fiber trees. In: Proceedings of the 4th annual European symposium on algorithms, LNCS, vol 1136, pp 460–470. Springer, Berlin
Kaklamanis C, Persiano P, Erlebach T, Jansen K (1997) Constrained bipartite edge coloring with applications to wavelength routing. In: Proceedings of the 24th international colloquium on automata, languages and programming, LNCS, vol 1256, pp 493–504. Springer, Berlin
Kumar SR, Panigrahy R, Russell A, Sundaram R (1997) A note on optical routing in trees. Inf Process Lett 62(6):295–300
Kumar V, Schwabe EJ (1997) Improved access to optical bandwidth in trees. In: Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms, pp 437–444
Laxman S, Mukherjee B (1999) Light trees: optical multicasting for improved performance in wavelength routed networks. IEEE Commun Mag 37(2):67–73
Leon-Garcia A, Widjaja I (2000) Communication networks: fundamental concepts and key architectures. McGraw-Hill, New York
Mihail M, Kaklamanis C, Rao S (1995) Efficient access to optical bandwidth. In: Proceedings of the 36th annual symposium on foundations of computer science, p 548
Nishizeki T, Kashiwag K (1990) On the 1.1 edge-coloring of multigraphs. SIAM J Discrete Math 3(3):391–410
Raghavan P, Upfal E (1994) Efficient routing in all-optical networks. In: Proceedings of the 26th annual ACM symposium on theory of computing, pp 134–143
Tarjan R (1985) Decomposition by clique separators. Discrete Math 55(2):221–232