Universidade Federal do Rio de Janeiro COPPE

Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia

Instituto de Matemática

 
Visualizar Meses
Visualizar Meses
Visualizar Flat
Visualizar Flat
Visualizar Semanas
Visualizar Semanas
Visualizar Dias
Visualizar Dias
Categorias
Categorias
Procurar
Procurar

Evento: 'Seminário de Grafos e Algoritmos dia 06/05/2015'

Eventos PESC (Palestras, Seminários, etc.)
Palestras, Seminários, etc. do PESC/COPPE/UFRJ.
Data: Wednesday, May 06, 2015 At 13:30
Duração: 2 Horas

O grupo de Grafos e Algoritmos da UFRJ convida a todos para o seminário a ser realizado em 06/05/2015 (Quarta-feira).

Local: PESC/COPPE
Sala: H-324B
Horário: 13:30h

Palestrante: Sulamita Klein, Professor Titular

Título: Complexity of Graph Sandwich Problems related to Partition Problems

Resumo:
In this talk we consider two decision problems. The first one is the Golumbic, Kaplan and Shamir decision sandwich problem for the property Π, where two graphs G1 = (V, E1) and G2 = (V, E2) are given, such that E1 ⊆ E2, plus the question whether there exists a graph G = (V, E), such that E1 ⊆ E ⊆ E2, and G satisfies property Π. The second one is the Feder, Hell, Klein and Motwani decision graph partition problem, where it is given a graph G and the question whether there is a partition for the vertex set of G into at most k sets V1, V2, . . . , Vk, which can have inner properties (like Vi being a clique, or an independent set, or no restriction) and external properties (like ViVj being completely adjacent, or completely non-adjacent, or no restriction).

We will discuss the complexity of the sandwich problem for properties or classes of graphs arising from partition problems.

Observações: Este seminario seraá apresentado como palestra convidada na conferência LAGOS 2015 (http://www.lia.ufc.br/lagos2015/). Sula é a mais recente professora Titular do grupo de Grafos e Algoritmos da UFRJ.

Consulte também a página de seminários do grupo de Grafos e Algoritmos (http://grafos.cos.ufrj.br/grafos/seminarios.php).



Procurar no Calendário

Powered by ExtCalendar 2

© 2017 PESC/COPPE - Programa de Engenharia de Sistemas e Computação

Cidade Universitária, Centro de Tecnologia, Bloco H, Sala 319
Caixa Postal: 68511 CEP: 21941-972 Fones: +55 21 3938-8672 / +55 21 3938-8673 Fax: +55 21 3938-8676
Rio de Janeiro - RJ - Brasil
Horário de atendimento da Secretaria: 2a. a 6a. de 7:00 às 16:00 horas (exceto feriados escolares)