On-line vertex-covering
From MaRDI portal
Publication:1770381
DOI10.1016/j.tcs.2004.08.015zbMath1070.68118OpenAlexW2076855469MaRDI QIDQ1770381
Vangelis Th. Paschos, Marc Demange
Publication date: 6 April 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.08.015
Related Items (14)
Further Results on Online Node- and Edge-Deletion Problems with Advice ⋮ Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Adding isolated vertices makes some greedy online algorithms optimal ⋮ Unnamed Item ⋮ The advice complexity of a class of hard online problems ⋮ Online node- and edge-deletion problems with advice ⋮ Online budgeted maximum coverage ⋮ A better list heuristic for vertex cover ⋮ On-line maximum-order induced hereditary subgraph problems ⋮ Paging with request sets ⋮ Mean analysis of an online algorithm for the vertex cover problem ⋮ Relaxing the irrevocability requirement for online graph algorithms ⋮ Algorithm for online 3-path vertex cover
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online algorithms. The state of the art
- An on-line graph coloring algorithm with sublinear performance ratio
- Lower bounds for on-line graph coloring
- Online independent sets.
- On-line and first fit colorings of graphs
- Algorithms for the on-line travelling salesman
This page was built for publication: On-line vertex-covering
