z-logo
open-access-imgOpen Access
Politopo baseado em distâncias para o problema clássico de coloração de vértices em grafos
Author(s) -
Bruno Dias,
Rosiane de Freitas,
Javier Marenco,
Nelson Maculan
Publication year - 2018
Language(s) - Portuguese
Resource type - Conference proceedings
DOI - 10.5753/etc.2018.3155
Subject(s) - combinatorics , physics , humanities , mathematics , philosophy
Neste trabalho, apresenta-se o modelo baseado em distâncias para o problema clássico de coloração de vértices em grafos (VCP). A formulação de programação linear inteira utiliza variáveis de decisão que representam a distância entre cores atribuídas para cada par de vértices distintos, no lugar de fornecer explicitamente tais cores. Mostra-se que há uma relação próxima entre esta formulação e o modelo baseado em orientação para o VCP, proposto também pelos autores deste trabalho. Em particular, prova-se que desigualdades indutoras de facetas para o modelo baseado em orientação podem ser traduzidas em desigualdades indutoras de facetas para o modelo baseado em distâncias e vice-versa.

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

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom