Repositório Digital

A- A A+

Maximum matching with ordering constraints is NP-complete

.

Maximum matching with ordering constraints is NP-complete

Mostrar registro completo

Estatísticas

Título Maximum matching with ordering constraints is NP-complete
Autor Ritt, Marcus Rolf Peter
Data 2009
Assunto Grafos
Gramatica : Grafos
Abstract A maximum weighted matching in a graph can be computed in polynomial time. In this paper we show that a variant, where the matching lias to respect additional ordering constraints between the vertices makes the problem NP-complete.
Tipo Relatório Técnico e de Pesquisa
URI http://hdl.handle.net/10183/126651
Arquivos Descrição Formato
000722872.pdf (296.0Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.