On-line maximum-order induced hereditary subgraph problems

DOI10.1111/j.1475-3995.2005.00497.xzbMath1063.90059OpenAlexW2110928170MaRDI QIDQ4670672

Vangelis Th. Paschos, Marc Demange, Xavier Paradon

Publication date: 22 April 2005

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2914

zbMATH Keywords

reductionon-line algorithmindependent setcliquehereditary property

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (2)

A survey on combinatorial optimization in dynamic environments ⋮ Adding isolated vertices makes some greedy online algorithms optimal

Cites Work

• Online algorithms. The state of the art
• An on-line graph coloring algorithm with sublinear performance ratio
• Lower bounds for on-line graph coloring
• On-line vertex-covering
• Online independent sets.
• On-line models and algorithms for max independent set
• Algorithms for the on-line travelling salesman

This page was built for publication: On-line maximum-order induced hereditary subgraph problems