Online Multi-Coloring with Advice
From MaRDI portal
Publication:3453285
DOI10.1007/978-3-319-18263-6_8zbMath1329.68297arXiv1409.1722OpenAlexW3003975899MaRDI QIDQ3453285
Kim S. Larsen, Marie G. Christ, Lene Monrad Favrholdt
Publication date: 20 November 2015
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1409.1722
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Online algorithms; streaming algorithms (68W27)
Related Items (2)
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
- 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 Accommodating Function: A Generalization of the Competitive Ratio
- Advice Complexity of Online Coloring for Paths
- On the Advice Complexity of the Knapsack Problem
- 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
- 1-Local 33/24-Competitive Algorithm for Multicoloring Hexagonal Graphs
- On the Advice Complexity of the k-Server Problem
- Online Multi-Coloring with Advice
- 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
- On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles
- 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
This page was built for publication: Online Multi-Coloring with Advice
