Advice complexity of maximum independent set in sparse and bipartite graphs
From MaRDI portal
Publication:2344218
DOI10.1007/s00224-014-9592-2zbMath1328.68313MaRDI QIDQ2344218
Stefan Dobrev, Rastislav Královič, Richard Královič
Publication date: 12 May 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-014-9592-2
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W27: Online algorithms; streaming algorithms
Related Items
Online Minimum Spanning Tree with Advice, The advice complexity of a class of hard online problems, Dynamic node packing, An efficient local search framework for the minimum weighted vertex cover problem, Optimal Online Edge Coloring of Planar Graphs with Advice
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Drawing maps with advice
- Online coloring of bipartite graphs with and without advice
- Semi-online preemptive scheduling: one algorithm for all variants
- Online computation with advice
- Trade-offs between the size of advice and broadcasting time in trees
- Local MST computation with short advice
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- Tree exploration with advice
- Fast radio broadcasting with advice
- Communication algorithms with advice
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Online independent sets.
- Vertex colouring and forbidden subgraphs -- a survey
- Distributed computing with advice: information sensitivity of graph coloring
- On-line graph coloring of \({\mathbb{P}_5}\)-free graphs
- On the Advice Complexity of the k-Server Problem
- On-line models and algorithms for max independent set
- Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- On-line and first fit colorings of graphs
- Graph Colorings
- Measuring the problem-relevant information in input