Online Multi-Coloring with Advice

被引：0
作者：
Christ, Marie G. [1 ]
Favrholdt, Lene M. [1 ]
Larsen, Kim S. [1 ]
机构：
[1] Univ Southern Denmark, Odense, Denmark
来源：
APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2014 | 2015年 / 8952卷
关键词：
FREQUENCY ALLOCATION; CHANNEL ASSIGNMENT; COMPLEXITY; ALGORITHM; LOCALITY; BOUNDS;
D O I：
10.1007/978-3-319-18263-6_8
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We consider the problem of online graph multi-coloring with advice. Multi-coloring is often used to model frequency allocation in cellular networks. We give several nearly tight upper and lower bounds for the most standard topologies of cellular networks, paths and hexagonal graphs. For the path, negative results trivially carry over to bipartite graphs, and our positive results are also valid for bipartite graphs. The advice given represents information that is likely to be available, studying for instance the data from earlier similar periods of time.
引用
收藏
页码：83 / 94
页数：12
相关论文
共 40 条
  • [1] On paging with locality of reference
    Albers, S
    Favrholdt, LM
    Giel, O
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2005, 70 (02) : 145 - 175
  • [2] [Anonymous], 1998, Online Computation and Competitive Analysis
  • [3] Barhum K, 2014, LECT NOTES COMPUT SC, V8327, P89, DOI 10.1007/978-3-319-04298-5_9
  • [4] Bianchi Maria Paola, 2012, Computing and Combinatorics. Proceedings of the 18th Annual International Conference COCOON 2012, P519, DOI 10.1007/978-3-642-32241-9_44
  • [5] Bianchi M.P., 2013, LNCS, P53
  • [6] Bökenhauer HJ, 2011, LECT NOTES COMPUT SC, V6755, P207, DOI 10.1007/978-3-642-22006-7_18
  • [7] Böockenhauer HJ, 2012, LECT NOTES COMPUT SC, V7256, P61, DOI 10.1007/978-3-642-29344-3_6
  • [8] Böckenhauer HJ, 2009, LECT NOTES COMPUT SC, V5878, P331, DOI 10.1007/978-3-642-10631-6_35
  • [9] COMPETITIVE PAGING WITH LOCALITY OF REFERENCE
    BORODIN, A
    IRANI, S
    RAGHAVAN, P
    SCHIEBER, B
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1995, 50 (02) : 244 - 258
  • [10] Boyar Joan, 2012, Algorithm Theory-SWAT 2012. Proceedings 13th Scandinavian Symposium and Workshops, P328, DOI 10.1007/978-3-642-31155-0_29
1234