Thema der Dissertation:
Enriched Periodic Timetabling Thema der Disputation:
Circuit Bases in Graphs
Enriched Periodic Timetabling Thema der Disputation:
Circuit Bases in Graphs
Abstract: Circuits are fundamental structures in graphs, capturing connectivity, dependence relations and redundancies in networks. They appear in a wide range of applications, from electrical networks, to chemical molecular graphs, and periodic timetabling. While the number of circuits in a graph can be exponential, it is possible to express each of them by a linear combination of a carefully chosen set of linearly independent circuits – a circuit basis.
We will discuss the different classes of circuit bases as have been studied in literature, including their characterisations. For graphs with associated arc-weights, one can define the minimum weight circuit basis problem, which asks for a circuit basis whose aggregated weight is minimal. The various classes give rise to variants of the minimum weight circuit basis problem – which differ in their complexity. We will shed light on algorithms for constructing solutions to the problems, key concepts, and, finally, their limitations.
We will discuss the different classes of circuit bases as have been studied in literature, including their characterisations. For graphs with associated arc-weights, one can define the minimum weight circuit basis problem, which asks for a circuit basis whose aggregated weight is minimal. The various classes give rise to variants of the minimum weight circuit basis problem – which differ in their complexity. We will shed light on algorithms for constructing solutions to the problems, key concepts, and, finally, their limitations.
Zeit & Ort
29.04.2026 | 16:00
Seminarraum 046
(Fachbereich Mathematik und Informatik, Takustr. 9, 14195 Berlin)