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 条
  • [31] ADVICE COMPLEXITY AND BARELY RANDOM ALGORITHMS
    Komm, Dennis
    Kralovic, Richard
    [J]. RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2011, 45 (02): : 249 - 267
  • [32] McDiarmid C, 2000, NETWORKS, V36, P114, DOI 10.1002/1097-0037(200009)36:2<114::AID-NET6>3.0.CO
  • [33] 2-G
  • [34] Narayanan L, 2002, W S PA DI C, P71
  • [35] Static frequency assignment in cellular networks (vol 29, pg 396, 2001)
    Narayanan, L
    Shende, S
    [J]. ALGORITHMICA, 2002, 32 (04) : 679 - 679
  • [36] Static frequency assignment in cellular networks
    Narayanan, L
    Shende, SM
    [J]. ALGORITHMICA, 2001, 29 (03) : 396 - 409
  • [37] Seibert Sebastian, 2013, Algorithms and Complexity. 8th International Conference, CIAC 2013. Proceedings, P345, DOI 10.1007/978-3-642-38233-8_29
  • [38] AMORTIZED EFFICIENCY OF LIST UPDATE AND PAGING RULES
    SLEATOR, DD
    TARJAN, RE
    [J]. COMMUNICATIONS OF THE ACM, 1985, 28 (02) : 202 - 208
  • [39] 2-local 4/3-competitive algorithm for multicoloring hexagonal graphs
    Sparl, P
    Zerovnik, J
    [J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2005, 55 (01): : 29 - 41
  • [40] Witkowski R, 2011, LECT NOTES COMPUT SC, V6732, P74
1234