The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex
DOI10.1137/18M1168704zbMath1432.57051OpenAlexW2982430530WikidataQ126867586 ScholiaQ126867586MaRDI QIDQ5241237
Sergio Cabello, William Pettersson, Stefan Kratsch, Benjamin A. Burton
Publication date: 30 October 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1168704
Analysis of algorithms and problem complexity (68Q25) General topology of complexes (57Q05) Triangulating manifolds (57Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-dimensional topology (including mapping class groups of surfaces, Teichmüller theory, curve complexes, etc.) (57K20)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Courcelle's theorem for triangulations
- Fundamentals of parameterized complexity
- Hardness results for homology localization
- The topology of four-dimensional manifolds
- The number of rooted triangular maps on a surface
- Einstein structures: Existence versus uniqueness
- Planar graphs, via well-orderly maps and trees
- Irreducible triangulations of surfaces with boundary
- A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- Annotating Simplices with a Homology Basis and Its Applications
- Fixed Parameter Tractable Algorithms in Combinatorial Topology
- Efficient algorithms to decide tightness
- A separator theorem for graphs of bounded genus
- A Census of Planar Triangulations
- Algorithms and Complexity for Turaev-Viro Invariants
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Color-coding
- A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number.
- Parameterized Algorithms
This page was built for publication: The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex
