Advice complexity of maximum independent set in sparse and bipartite graphs
From MaRDI portal
Publication:2344218
DOI10.1007/s00224-014-9592-2zbMath1328.68313OpenAlexW2106260425MaRDI 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
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Online algorithms; streaming algorithms (68W27)
Related Items (6)
Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ The advice complexity of a class of hard online problems ⋮ Advice complexity of adaptive priority algorithms ⋮ An efficient local search framework for the minimum weighted vertex cover problem ⋮ Online Minimum Spanning Tree with Advice ⋮ Dynamic node packing
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
This page was built for publication: Advice complexity of maximum independent set in sparse and bipartite graphs
