Online Multi-Coloring with Advice

DOI10.1007/978-3-319-18263-6_8MaRDI QIDQ3453285zbMATHOpenAlexFDO

Authors Marie G. Christ, Kim S. Larsen, Lene M. 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

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Abstract: 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.

Recommendations

• Online multi-coloring with advice
• Advice complexity of the online coloring problem
• scientific article; zbMATH DE number 7758354
• Online hypergraph coloring
• scientific article; zbMATH DE number 65699
• scientific article; zbMATH DE number 1875408
• Advice complexity of online coloring for paths
• Online coloring known graphs
• Three topics in online list coloring
• Online coloring of bipartite graphs with and without advice

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• 1-Local 33/24-Competitive Algorithm for Multicoloring Hexagonal Graphs
• 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
• Absolute and asymptotic bounds for online frequency allocation in cellular networks
• Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
• Advice complexity and barely random algorithms
• Advice complexity of online coloring for paths
• Advice complexity of the online coloring problem
• Better bounds for incremental frequency allocation in bipartite graphs
• Channel assignment and weighted coloring
• Competitive paging with locality of reference
• Competitive snoopy caching
• Corrigendum: Static frequency assignment in cellular networks
• Distributed Online Frequency Assignment in Cellular Networks
• Extending the accommodating function
• Frequency Allocation Problems for Linear Cellular Networks
• Information complexity of online problems
• Measuring the problem-relevant information in input
• On paging with locality of reference
• On the Advice Complexity of Online Problems
• On the advice complexity of buffer management
• On the advice complexity of the \(k\)-server problem
• On the advice complexity of the knapsack problem
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
• On the advice complexity of the set cover problem
• On the power of advice and randomization for the disjoint path allocation problem
• Online Multi-Coloring with Advice
• Online bin packing with advice
• Online coloring of bipartite graphs with and without advice
• Online computation with advice
• Online multi-coloring on the path revisited
• Static frequency assignment in cellular networks
• The accommodating function: A generalization of the competitive ratio
• The seat reservation problem
• Three results on frequency assignment in linear cellular networks
• Universal codeword sets and representations of the integers

Cited in

(3)

• Online multi-coloring with advice
• Tight lower bounds for the complexity of multicoloring
• Online Multi-Coloring with Advice

This page was built for publication: Online Multi-Coloring with Advice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453285)