SMS scnews item created by Zhou Zhang at Tue 12 Nov 2013 0105
Type: Seminar
Modified: Tue 12 Nov 2013 1205
Distribution: World
Expiry: 10 Dec 2013
Calendar1: 18 Nov 2013 1200-1300
CalLoc1: AGR Carslaw 829
Auth: zhangou@60.225.178.103 (zhouz) in SMS-WASM

# GTA Seminar : Spreer -- Parameterized Complexity of Discrete Morse Theory

Speaker: Dr. Jonathan Spreer (Queensland)

http://www.smp.uq.edu.au/node/106/1142

Time: **Monday**, Nov. 18, 12NOON--1PM

Room: AGR (Carslaw 829)

Lunch: after the talk, at Law Annex Cafe.

----------------------------------------------

Title: Parameterized Complexity of Discrete Morse Theory

Abstract: Optimal Morse matchings reveal essential structures
of cell complexes which lead to powerful tools to study discrete
3-manifolds. However, such matchings are known to be NP-hard to
compute on 3-manifolds. Here, we refine the study of the complexity
of problems related to discrete Morse theory in terms of parameterized
complexity. On the one hand we prove that the erasability problem
is W[P]-complete on the natural parameter. On the other hand we
propose an algorithm for computing optimal Morse matchings on
triangulations of 3-manifolds which is fixed-parameter tractable
in the treewidth of the dual graph of the triangulation as well
as the bipartite graph representing the adjacency of the 1- and
2-simplexes.

This is joint work with Ben Burton, Thomas Lewiner and Joao Paixao.

----------------------------------------------

Seminar website:

http://www.maths.usyd.edu.au/u/SemConf/Geometry/


Actions:
Calendar (ICS file) download, for import into your favourite calendar application
UNCLUTTER for printing
AUTHENTICATE to mark the scnews item as read
School members may try to .
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.714333713054657, "perplexity": 7706.262486625133}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2022-49/segments/1669446711218.21/warc/CC-MAIN-20221207185519-20221207215519-00378.warc.gz"}