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
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
