BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Fine-Grained Complexity of Computing Degree-Constrained Spanning T
 rees [Oberseminar Discrete Optimization]
DTSTART:20250324T171500Z
DTEND:20250324T181500Z
DTSTAMP:20260916T032300Z
UID:indico-event-276@math-events.uni-bonn.de
DESCRIPTION:Speakers: Phuc Hung Hong (Technische Universität Wien)\n\nThi
 s talk is concerned with the computation of minimum-cost spanning trees sa
 tisfying prescribed vertex degree constraints: Given a graph G and a const
 raint function D\, we ask for a (minimum-cost) spanning tree T such that f
 or each vertex v\, the degree of v in T is in a set D(v) of admissible deg
 rees. We obtain an almost-complete overview of the fine-grained complexity
  of these problems taking into account the most classical graph parameters
  of the input graph G. \nIn particular\, we show SETH-tight upper and lowe
 r bounds when parameterized by the pathwidth and cutwidth\, an ETH-tight a
 lgorithm parameterized by the cliquewidth\, and a nearly SETH-tight algor
 ithm parameterized by treewidth.\nJoint work with Narek Bojikian\, Alexand
 er Firbas\, Robert Ganian and Krisztina Szilagyi.\n \nThe Oberseminar tak
 es place in the Seminarraum\, 1st floor. Participants are invited to have 
 coffee or tea in the lounge before.\n \n\nhttps://math-events.uni-bonn.de
 /event/276/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/276/
END:VEVENT
END:VCALENDAR