Optimal Online Edge Coloring of Planar Graphs with Advice
From MaRDI portal
Publication:2947032
DOI10.1007/978-3-319-18173-8_26zbMath1459.68233arXiv1410.7923OpenAlexW1926385644MaRDI QIDQ2947032
Publication date: 21 September 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1410.7923
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Online algorithms; streaming algorithms (68W27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online coloring of bipartite graphs with and without advice
- Online algorithms with advice for bin packing and scheduling problems
- On the list update problem with advice
- Online computation with advice
- Competitive snoopy caching
- The greedy algorithm is optimal for on-line edge coloring
- A new measure for the study of on-line algorithms
- Competitive paging with locality of reference
- Advice complexity of maximum independent set in sparse and bipartite graphs
- Online makespan minimization with parallel schedules
- The online knapsack problem: advice and randomization
- New linear-time algorithms for edge-coloring planar graphs
- Advice Complexity of Online Coloring for Paths
- Online Graph Exploration with Advice
- Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem
- On the Advice Complexity of the k-Server Problem
- Reordering Buffer Management with Advice
- Improved edge-coloring algorithms for planar graphs
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- The NP-Completeness of Edge-Coloring
- Edge-Coloring and f-Coloring for Various Classes of Graphs
- Beyond Competitive Analysis
- Advice Complexity of the Online Coloring Problem
- Measuring the problem-relevant information in input
This page was built for publication: Optimal Online Edge Coloring of Planar Graphs with Advice
