On-line models and algorithms for max independent set | Zendy

Bruno Escoffier | Zendy; Vangélis Th. Paschos | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On-line models and algorithms for max independent set

Author(s) -

Bruno Escoffier,

Vangélis Th. Paschos

Publication year - 2006

Publication title -

rairo - operations research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.383

H-Index - 24

eISSN - 1290-3868

pISSN - 0399-0559

DOI - 10.1051/ro:2006014

Subject(s) - backtracking , vertex (graph theory) , graph , line graph , computation , computer science , combinatorics , algorithm , graph algorithms , line (geometry) , mathematics , geometry

In on-line computation, instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially present (in our case the complete graph on the order n of the final graph) and edges are progressively

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research