On-line maximum-order induced hereditary subgraph problems

DOI10.1111/J.1475-3995.2005.00497.XMaRDI QIDQ4670672zbMATH OpenOpenAlexFDO

Authors Marc Demange, Xavier Paradon, Vangelis Th. Paschos

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

cliquehereditary propertyindependent seton-line algorithmreduction

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 2079869
• Algorithms and Computation
• Reducing off-line to on-line: An example and its applications
• On-line computation and maximum-weighted hereditary subgraph problems
• Advice complexity of the online induced subgraph problem

Cites work

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

Cited in

(6)

• On-line computation and maximum-weighted hereditary subgraph problems
• A survey on combinatorial optimization in dynamic environments
• Reoptimization of maximum weight induced hereditary subgraph problems
• scientific article; zbMATH DE number 2079869 (Why is no real title available?)
• Reducing off-line to on-line: An example and its applications
• Algorithms and Computation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4670672)