BEGIN:VCALENDAR
VERSION:2.0
METHOD:PUBLISH
CALSCALE:GREGORIAN
PRODID:-//WordPress - MECv6.2.0//EN
X-ORIGINAL-URL:https://www.inesc-id.pt/
X-WR-CALNAME:INESC-ID
X-WR-CALDESC:25 Years Defining Technology
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-PUBLISHED-TTL:PT1H
X-MS-OLK-FORCEINSPECTOROPEN:TRUE
BEGIN:VEVENT
CLASS:PUBLIC
UID:MEC-8396b14c5dff55d13eea57487bf8ed26@inesc-id.pt
DTSTART:20210916T150000Z
DTEND:20210916T170000Z
DTSTAMP:20210915T100700Z
CREATED:20210915
LAST-MODIFIED:20210915
PRIORITY:5
TRANSP:OPAQUE
SUMMARY:Seminar “Coping with NP-hard problems by using parameterized algorithms”
DESCRIPTION:Seminar with Professor Jan Arne Telle, Department of Informatics,  ( https://www.uib.no/en/persons/Jan.Arne.Telle )University of Bergen\n16 september 2021, 4PM\nRoom 336 INESC-ID\n“Coping with NP-hard problems by using parameterized algorithms”\nThe talk will give an introduction to the field of parameterized complexity, which focuses on classifying computational problems according to their inherent difficulty with respect to /multiple/ parameters of the input. The complexity of a problem is then measured as a function of those parameters.\nThis allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input.\nWe will give some concrete applications:\n1 A kernelization algorithm for k-Vertex Cover (k-VC, use natural parameter).\n2 A Fixed Parameter Tractable (FPT) algorithm for k-VC.\n3 Dominating Set (DS) is not FPT for the natural parameter.\n4 Introduce Treewidth tw.\n5 DS is FPT parameterized by tw.\n6 A hierarchy of graph parameters.\n7 An application to satisfiability\n
URL:https://www.inesc-id.pt/events/seminar-coping-with-np-hard-problems-by-using-parameterized-algorithms/
CATEGORIES:Events,Seminars & Lectures
ATTACH;FMTTYPE=image/jpeg:https://www.inesc-id.pt/wp-content/uploads/2021/09/picture-8663-1491212093-1.jpg
END:VEVENT
END:VCALENDAR