Parameterized Complexity of Discrete Morse Theory
DOI10.1145/2738034zbMath1347.68165arXiv1303.7037WikidataQ113310253 ScholiaQ113310253MaRDI QIDQ2828168
Jonathan Spreer, Thomas Lewiner, Benjamin A. Burton, João Paixão
Publication date: 24 October 2016
Published in: ACM Transactions on Mathematical Software, Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1303.7037
treewidth; collapsibility; fixed parameter tractability; fixed-parameter tractability; parameterized complexity; computational topology; discrete Morse theory; erasability; alternating cycle-free matching; W[P-completeness]; W[\(P\)-completeness]
68Q25: Analysis of algorithms and problem complexity
68W05: Nonnumerical algorithms
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
57Q15: Triangulating manifolds
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Uses Software