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: 'Palestra do Professor Leo Liberti, Ecole Polytechnique (X), França'

Notícias do PESC
Divulgação de Notícias do PESC.
Data: Monday, August 15, 2011 At 10:00
Duração: Todo dia

Universidade Federal do Rio de Janeiro
COPPE-Programa de Engenharia de Sistemas e Computação
INCT - Web Sience

Data: 15 de agosto de 2011 (segunda-feira)
Horário: 10h00
Local: Bolco H, sala H-324A do CT-UFRJ, Ilha do Fundão


PALESTRA

The amazing mathematics of proteins

por

Leo LIBERTI
Professor Associado, Ecole Polytechnique (X), França
(http://www.lix.polytechnique.fr/~liberti/)


Abstract
The graph embedding problem consists in finding an embedding x:V->R^K of a simple weighted undirected graph G=(V,E,d) such that for each edge {u,v} we have ||x(u) - x(v)|| = d(u,v).
Although the problem in general requires a search in continuous space, we restrict attention to a subclass of instances for which there is a vertex order that allows for a discrete search. This subclass is still NP-hard. Here's a strange occurrence which we noticed in 2005: every instance yields a number of solutions which is a power of two. Five years since, we managed to prove that this conjecture holds with probability 1. Using the same theoretical set-up we also exhibit some sufficient conditions for which the problem is in P. Interestingly, all tested protein graphs satisfy these conditions, thus providing an important application to this problem.



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)