Advanced search
Start date
Betweenand

Complexity of PQR Tree Construction

Grant number: 10/04071-1
Support Opportunities:Scholarships in Brazil - Master
Effective date (Start): September 01, 2010
Effective date (End): February 29, 2012
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:João Meidanis
Grantee:João Paulo Pereira Zanetti
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

This project intends to investigate the computational complexity of PQR tree construction. PQR trees are data structures relevant for the problem of permuting the columns of a binary matrix in order to leave their rows with all their 1s in consecutive positions, with applications in planarity, interval graphs, and problems in computational biology. Both online and offline algorithms will be investigated.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
ZANETTI, João Paulo Pereira. Complexity of PQR tree construction. 2012. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.

Please report errors in scientific publications list using this form.