Volume 20, issue 2 (2016)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 28
Issue 3, 1005–1499
Issue 2, 497–1003
Issue 1, 1–496

Volume 27, 9 issues

Volume 26, 8 issues

Volume 25, 7 issues

Volume 24, 7 issues

Volume 23, 7 issues

Volume 22, 7 issues

Volume 21, 6 issues

Volume 20, 6 issues

Volume 19, 6 issues

Volume 18, 5 issues

Volume 17, 5 issues

Volume 16, 4 issues

Volume 15, 4 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 5 issues

Volume 11, 4 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 3 issues

Volume 7, 2 issues

Volume 6, 2 issues

Volume 5, 2 issues

Volume 4, 1 issue

Volume 3, 1 issue

Volume 2, 1 issue

Volume 1, 1 issue

The Journal
About the Journal
Editorial Board
Editorial Procedure
Subscriptions
 
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
 
ISSN (electronic): 1364-0380
ISSN (print): 1465-3060
Author Index
To Appear
 
Other MSP Journals
On the complexity of immersed normal surfaces

Benjamin A Burton, Éric Colin de Verdière and Arnaud de Mesmay

Geometry & Topology 20 (2016) 1061–1083
Bibliography
1 I Agol, J Hass, W Thurston, The computational complexity of knot genus and spanning area, Trans. Amer. Math. Soc. 358 (2006) 3821 MR2219001
2 I R Aitchison, S Matsumoto, J H Rubinstein, Surfaces in the figure-8 knot complement, J. Knot Theory Ramifications 7 (1998) 1005 MR1671559
3 S Arora, B Barak, Computational complexity: a modern approach, Cambridge Univ. Press (2009) MR2500087
4 B A Burton, T Lewiner, J Paixão, J Spreer, Parameterized complexity of discrete Morse theory, from: "Computational geometry", Association for Computing Machinery (2013) 127 MR3208204
5 B A Burton, J Spreer, The complexity of detecting taut angle structures on triangulations, from: "Proceedings of the 24th Annual ACM–SIAM Symposium on Discrete Algorithms", Society for Industrial and Applied Mathematics (2012) 168 MR3185388
6 É Colin de Verdière, Topological algorithms for graphs on surfaces, Habilitation thesis, École normale supérieure (2012)
7 N Creignou, S Khanna, M Sudan, Complexity classifications of Boolean constraint satisfaction problems, Society for Industrial and Applied Mathematics (2001) MR1827376
8 V Dalmau, D K Ford, Generalized satisfiability with limited occurrences per variable: a study through delta-matroid parity, from: "Mathematical foundations of computer science" (editors B Rovan, P Vojtáš), Lecture Notes in Comput. Sci. 2747, Springer (2003) 358 MR2081586
9 T Feder, Fanout limitations on constraint systems, Theoret. Comput. Sci. 255 (2001) 281 MR1819077
10 M R Fellows, Parameterized complexity: new developments and research frontiers, from: "Aspects of complexity" (editors R Downey, D Hirschfeldt), de Gruyter Ser. Log. Appl. 4, de Gruyter (2001) 51 MR1884261
11 C Gordon, The theory of normal surfaces, lecture notes (2001)
12 W Haken, Theorie der Normalflächen, Acta Math. 105 (1961) 245 MR0141106
13 J Hass, J C Lagarias, N Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999) 185 MR1693203
14 A Hatcher, Notes on basic 3–manifold topology, (2007)
15 G Kuperberg, Knottedness is in NP, modulo GRH, Adv. Math. 256 (2014) 493 MR3177300
16 D M Letscher, Immersed normal surfaces and decision problems for 3–manifolds, PhD thesis, University of Michigan (1997)
17 J Matoušek, B Gärtner, Understanding and using linear programming, Springer (2007)
18 S Matsumoto, R Rannard, The regular projective solution space of the figure-eight knot complement, Experiment. Math. 9 (2000) 221 MR1780207
19 E E Moise, Affine structures in 3–manifolds, V : The triangulation theorem and Hauptvermutung, Ann. of Math. 56 (1952) 96 MR0048805
20 R Rannard, Computing immersed normal surfaces in the figure-eight knot complement, Experiment. Math. 8 (1999) 73 MR1685039
21 T J Schaefer, The complexity of satisfiability problems, from: "Tenth Annual ACM Symposium on Theory of Computing", ACM (1978) 216 MR521057
22 A Schrijver, Combinatorial optimization : polyhedra and efficiency, Volume A, 24, Springer (2003) MR1956924
23 J Stillwell, Classical topology and combinatorial group theory, 72, Springer (1993) MR1211642