Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2024

Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional

Abstract

Temporal graphs are graphs that evolve over time. Many problems which are polynomial-time solvable in standard graphs become NP-hard when appropriately defined in the realm of temporal graphs. This suggested the definition of several parameters for temporal graphs and to prove the fixed-parameter tractability of several problems with respect to these parameters. In this paper, we introduce a hierarchy of parameters based on the previously defined interval membership width and on the temporal evolution of the connected components of the under- lying static graph. We then show that the Eulerian trail problem and the temporal 2-coloring problem are both fixed-parameter tractable (in short, FPT) with respect to any of the parameters in the hierarchy. We also introduce a vertex-variant of the parameters and we show that the firefighter problem (which was known to be FPT with respect to the vertex-variant of the interval membership width) is also FPT with respect to one of the parameters in the second level of the hierarchy.
Fichier principal
Vignette du fichier
MakingtheIntervalMembershipWidthof0ATemporalGraphsConnectedandBidirectional.pdf (557.34 Ko) Télécharger le fichier

Dates and versions

lirmm-04702099 , version 1 (19-09-2024)

Identifiers

Cite

Filippos Christodoulou, Andrea Marino, Ana Silva, Pierluigi Crescenzi, Dimitrios M. Thilikos. Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional. IWOCA 2024 - 35th International Workshop on Combinatorial Algorithms, Jul 2024, Ischia, Italy. pp.247-258, ⟨10.1007/978-3-031-63021-7_19⟩. ⟨lirmm-04702099⟩
17 View
9 Download

Altmetric

Share

More