Online multi-coloring with advice
From MaRDI portal
Publication:2355706
DOI10.1016/j.tcs.2015.06.044zbMath1328.68312MaRDI QIDQ2355706
Kim S. Larsen, Marie G. Christ, Lene Monrad Favrholdt
Publication date: 24 July 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.06.044
competitive analysis; online algorithms; frequency allocation; advice complexity; graph multi-coloring
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
68W27: Online algorithms; streaming algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Online multi-coloring on the path revisited
- Better bounds for incremental frequency allocation in bipartite graphs
- Online computation with advice
- On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
- Three results on frequency assignment in linear cellular networks
- Competitive snoopy caching
- Corrigendum: Static frequency assignment in cellular networks
- Extending the accommodating function
- Competitive paging with locality of reference
- The seat reservation problem
- The online knapsack problem: advice and randomization
- The Accommodating Function: A Generalization of the Competitive Ratio
- Advice Complexity of Online Coloring for Paths
- Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
- On the Advice Complexity of the Set Cover Problem
- Online Coloring of Bipartite Graphs with and without Advice
- On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
- On the Advice Complexity of the k-Server Problem
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- Universal codeword sets and representations of the integers
- Distributed Online Frequency Assignment in Cellular Networks
- Channel assignment and weighted coloring
- 2-local <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-competitive algorithm for multicoloring hexagonal graphs
- On the Advice Complexity of Buffer Management
- Advice Complexity of the Online Coloring Problem
- Advice Complexity and Barely Random Algorithms
- Measuring the problem-relevant information in input
- Frequency Allocation Problems for Linear Cellular Networks
- On paging with locality of reference
- Static frequency assignment in cellular networks
- Absolute and asymptotic bounds for online frequency allocation in cellular networks