HS2024: 53085 Graph Theory and Applications

In this course, we first introduce some basic concepts and notions of graph theory. We then present a series of graph theoretical problems with real world applications. Some of them are, unfortunately, hard to solve in general. Hence, in the rest of the course, we focus on solving these problems efficiently on classes of graphs that enjoy specific structural properties.

Allgemeine Informationen

Kursbeschreibung
In this course, we first introduce some basic concepts and notions of graph theory. We then present a series of graph theoretical problems and invariants with real world applications. Some of them are, unfortunately, hard to compute in general. Hence, in the rest of the course, we focus on solving these problems efficiently on classes of graphs that enjoy specific structural properties.
Kursprogramm
1. Introduction: basic notions and definitions

2. Some classic invariants: independence number (α), clique number (ω), vertex cover number (τ), matching number (ν), chromatic number (χ), and chromatic index (χ′)
• Definitions and overview
• Relations between invariants
• Distinguish their computational complexity on general graphs
• Real-life motivations
• Bounds and relations on the corresponding invariants on general graphs

3. Some restricted graph classes [most lectures will be part of this chapter]
• Bipartite graphs
• Chordal graphs and subclasses
• Planar graphs

Beschreibung

In this course, we first introduce some basic concepts and notions of graph theory. We then present a series of graph theoretical problems with real world applications. Some of them are, unfortunately, hard to solve in general. Hence, in the rest of the course, we focus on solving these problems efficiently on classes of graphs that enjoy specific structural properties.

Allgemein

Sprache
Englisch
Copyright
This work has all rights reserved by the owner.

Verfügbarkeit

Zugriff
Unbegrenzt – wenn online geschaltet
Aufnahmeverfahren
Sie können diesem Kurs direkt beitreten.
Zeitraum für Beitritte
Unbegrenzt

Für Kursadministratoren freigegebene Daten

Daten des Persönlichen Profils
Anmeldename
Vorname
Nachname
E-Mail