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 Otimização: Profa. Rosa Maria Videira de Figueiredo CANCELADA'

Eventos PESC (Palestras, Seminários, etc.)
Palestras, Seminários, etc. do PESC/COPPE/UFRJ.
Data: Thursday, January 06, 2011 At 10:00
Duração: 2 Horas

***
CANCELADA por motivo de doença da palestrante.
***
Data: quinta-feira, 06 de janeiro de 2011
Local: sala H-324B do Centro de Tecnologia, Ilha do Fundão, UFRJ
Horário: 10h00

Título: The maximum k-balanced subgraph problem

por

Profa. Rosa Maria Videira de Figueiredo
Universidade do Estado do Rio de Janeiro (UERJ) e
Universidade de Aveiro (Portugal)

Resumo:
Let G=(V,E) be an undirected graph and let s be a function that assigns a sign to each edge in E: G together with s is called a signed graph.
Consider a parameter k. A signed graph is k-balanced if V can be partitioned into at most k sets in such a way that positive edges are found only within the sets and negative edges go between sets.
The maximum k-balanced subgraph problem is the problem of finding a subgraph of G that is k-balanced and maximum according to the number of vertices.
The general case has applications in clustering problems appearing in collaborative/conflicting environments. The particular case defined for k=2 has an application in the detection of a network structure in a matrix.
We present a 0-1 linear programming formulation for this problem and propose an exact algorithm for its solution.


Responsável:
Nelson Maculan
Universidade Federal do Rio de Janeiro
COPPE-Engenharia de Sistemas e Computação
Caixa Postal 68511
21941-972 Rio de Janeiro, RJ, Brasil
Tel.: + 55 21 25628708
E-mail: maculan@cos.ufrj.br


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)