BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20251104T163000
DTEND;TZID=Asia/Seoul:20251104T173000
DTSTAMP:20260416T111620
CREATED:20250904T053024Z
LAST-MODIFIED:20250904T053024Z
UID:11544-1762273800-1762277400@dimag.ibs.re.kr
SUMMARY:Ahmed Ghazy and Tim Hartmann\, Continuous Graphs – An Overview and a Coloring Problem
DESCRIPTION:We consider a continuous model of graphs\, introduced by Dearing and Francis in 1974\, where each edge of G to be a unit interval\, giving rise to an infinite metric space that contains not only the vertices of G but all points on all edges of G. Several standard graph problems can be defined and studied on continuous graphs\, yielding many surprising algorithmic results and combinatorial connections. \nThe motivation can be exemplified by the well-known Independent Set problem on graphs. Given a graph G\, we want to place k facilities that are pairwise at least a distance 2 edge lengths apart. In some applications\, such as when the underlying graph represents a street network\, it is reasonable to allow placing a facility not only at a crossroad but also somewhere within a street\, that is\, not only at a vertex but also at any point on an edge between two vertices. This motivates the study of the Independent Set problem on continuous graphs. In such a setting\, for example\, the problem corresponds to requiring pairwise distance r=2 for the placed facilities. However\, we may also study the problem where we fix r to any positive integer\, rational\, or even irrational number. Other problems studied in the continuous model include Dominating Set\, TSP\, and Coloring. \nIn the first part of this talk\, we will give a general overview of research on continuous graphs and computational problems in this setting. \nIn the second part\, we explore\, as part of recent work\, a coloring problem on continuous graphs akin to the well-known Hadwiger-Nelson Problem. \nBased on joint work with Fabian Frei\, Florian Hörsch\, Tom Janßen\, Stefan Lendl\, Dániel Marx\, Prahlad Narasimhan\, and Gerhard Woeginger.
URL:https://dimag.ibs.re.kr/event/2025-11-04/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR