[Mittagsseminar TI] Mittagsseminar am Di. 18.03.2025

[Kristin Knorr <knorrkri@zedat.fu-berlin.de>]

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin 
spricht am

Dienstag, 18.03.2025, 12:00 Uhr, , SR 055, Takustraße 9
Robert Scheffler (BTU Cottbus)
zum Thema: Simultaneous Representations meet Graph Width Parameters: The 
Simultaneous Interval Number and the Simultaneous Chordal Number

Abstract:
We propose a novel way of generalizing the classes of interval and 
chordal graphs via graph width parameters called simultaneous interval 
number and simultaneous chordal number. These parameters are related to 
the simultaneous representation problem for interval (chordal) graphs 
and are defined as the smallest number d of labels such that the graph 
admits a d-simultaneous interval (chordal) representation, that is, an 
assignment of intervals (subtrees of a tree) and label sets to the 
vertices such that two vertices are adjacent if and only if the 
corresponding intervals (subtrees) as well as their label sets intersect.
We discuss the complexity of computing these parameters and give several 
bounds for the parameters, showing in particular their relation to 
pathwidth and treewidth. Furthermore, we discuss FPT algorithms and 
hardness results for problems like Clique, Independent Set, Dominating 
Set and Coloring.