Online Interval Coloring
- PDF / 220,488 Bytes
- 5 Pages / 547.087 x 737.008 pts Page_size
- 106 Downloads / 181 Views
O
Online Interval Coloring
BST remains open. Several attempts have been made to improve the lower bound [6,7,22], but none of them have led to a lower competitive ratio. Even in the off-line model, the problem of finding an O(1)-competitive BST is difficult. The best known off-line constant competitive algorithm uses dynamic programming and requires exponential time. Cross References B-trees Degree-Bounded Trees Dynamic Trees Recommended Reading Based on Wilber [22]’s lower bound, Tango [6] is the first O(log log n)-competitive binary search tree. Using many of the ideas in Tango and Link-cut Trees [14,19], MultiSplay Trees [21] generalize the competitive framework to include insertion and deletion. The recommended readings are Self-adjusting binary search trees by Sleator and Tarjan, Lower bounds for accessing binary search trees with rotations by Wilber, Dynamic Optimality - Almost by Demaine, et al, and O(log log n) dynamic competitive binary search tree by Wang, et al.
12. Luccio, F., Pagli, L.: On the upper bound on the rotation distance of binary trees. Inf. Process. Lett. 31(2), 57–60 (1989) 13. Mäkinen, E.: On the rotation distance of binary trees. Inf. Process. Lett. 26(5), 271–272 (1988) 14. Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652–686 (1985) 15. Sleator, D.D., Tarjan, R.E., Thurston, W.P.: Rotation distance, triangulations, and hyperbolic geometry. In: Proceedings 18th ACM Symposium on Theory of Computing (STOC), Berkeley, 1986, pp. 122–135 16. Sundar, R.: Twists, turns, cascades, deque conjecture, and scanning theorem. In: Proceedings 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 555–559 (1989) 17. Sundar, R.: On the deque conjecture for the splay algorithm. Combinatorica 12(1), 95–124 (1992) 18. Tarjan, R.: Sequential access in play trees takes linear time. Combinatorica 5(4), 367–378 (1985) 19. Tarjan, R.E.: Data structures and network algorithms, CBMS-NSF Reg. Conf. Ser. Appl. Math., vol. 44. SIAM, Philadelphia, PA (1983) 20. Wang, C.C.: Multi-splay trees. Ph.D. Thesis, Carnegie Mellon University (2006) 21. Wang, C.C., Derryberry, J., Sleator, D.D.: O(log log n)-competitive dynamic binary search trees. In: Proc. 17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), Miami, 2006, pp. 374–383 22. Wilber, R.: Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. 18(1), 56–67 (1989)
Online Interval Coloring 1981; Kierstead, Trotter
1. Blum, A., Chawla, S., Kalai, A.: Static optimality and dynamic search-optimality in lists and trees. Algorithmica 36, 249–260 (2003) 2. Cole, R.: On the dynamic finger conjecture for splay trees II: The proof. SIAM J. Comput. 30(1), 44–85 (2000) 3. Cole, R., Mishra, B., Schmidt, J., Siegel, A.: On the dynamic finger conjecture for splay trees I: Splay sorting log n-block sequences. SIAM J. Comput. 30(1), 1–43 (2000) 4. Crane, C.A.: Linear lists and priority queues as balanced binary trees. Technical Report STAN-CS-72-259, Computer Science Dept., Stanford University (1972) 5. C
Data Loading...
