On-line vertex-covering

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

zbMATH Keywords

ApproximationCompetitive ratioGraphOn-line algorithmVertex-covering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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