XINFORMAÇÕES SOBRE DIREITOS AUTORAIS
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital
Título: ANALYSIS OF MORSE MATCHINGS: PARAMETERIZED COMPLEXITY AND STABLE MATCHING Autor: JOAO ANTONIO RECIO DA PAIXAO
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Colaborador(es):
THOMAS LEWINER - ADVISOR
Nº do Conteudo: 56591
Catalogação: 16/12/2021 Idioma(s): ENGLISH - UNITED STATES
Tipo: TEXT Subtipo: THESIS
Natureza: SCHOLARLY PUBLICATION
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=56591@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=56591@2
Referência DOI: https://doi.org/10.17771/PUCRio.acad.56591
Resumo:
Título: ANALYSIS OF MORSE MATCHINGS: PARAMETERIZED COMPLEXITY AND STABLE MATCHING Autor: JOAO ANTONIO RECIO DA PAIXAO
Nº do Conteudo: 56591
Catalogação: 16/12/2021 Idioma(s): ENGLISH - UNITED STATES
Tipo: TEXT Subtipo: THESIS
Natureza: SCHOLARLY PUBLICATION
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=56591@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=56591@2
Referência DOI: https://doi.org/10.17771/PUCRio.acad.56591
Resumo:
Morse theory relates the topology of a space to the critical elements of a
scalar function defined on it. This applies in both the classical theory and
a discrete version of it defined by Forman in 1995. Those Morse theories
permit to characterize a topological space from functions defined on it, but
also to study functions based on topological constructions it implies, such as
the Morse-Smale complex. While discrete Morse theory applies on general
cell complexes in an entirely combinatorial manner, which makes it suitable
for computation, the functions it considers are not sampling of continuous
functions, but special matchings in the graph encoding the cell complex
adjacencies, called Morse matchings.
When using this theory to study a topological space, one looks for optimal
Morse matchings, i.e. one with the smallest number of critical elements, to
get highly succinct topological information about the complex. The first
part of this thesis investigates the parameterized complexity of finding such
optimal Morse matching. On the one hand the Erasability problem, a
closely related problem to finding optimal Morse matchings, is proven to be
W[P]-complete. On the other hand, an algorithm is proposed for computing
optimal Morse matchings on triangulations of 3-manifolds which is fixed parameter
tractable in the tree-width of its dual graph.
When using discrete Morse theory to study a scalar function defined on
the space, one looks for a Morse matching that captures the geometric
information of that function. The second part of this thesis introduces a
construction of Morse matchings based on stable matchings. The theoretical
guarantees about the relation of such matchings to the geometry are
established through surprisingly simple proofs that benefits from the local
characterization of the stable matching. The construction and its guarantees
work in any dimension. Finally stronger results are obtained if the function
is discrete smooth on the complex, a notion defined in this thesis.
Descrição | Arquivo |
COMPLETE |