2026-07-28T23:34:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12693 2024-03-06T10:50:35Z ddc:004 open_access

Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs Conte, Alessio Crescenzi, Pierluigi Marino, Andrea Punzi, Giulia minimal cutset temporal graph minimal separator directed acyclic graph Temporal graphs are graphs in which arcs have temporal labels, specifying at which time they can be traversed. Motivated by recent results concerning the reliability analysis of a temporal graph through the enumeration of minimal cutsets in the corresponding line graph, in this paper we attack the problem of enumerating minimal s-d separators in s-d directed acyclic graphs (in short, s-d DAGs), also known as 2-terminal DAGs or s-t digraphs. Our main result is an algorithm for enumerating all the minimal s-d separators in a DAG with O(nm) delay, where n and m are respectively the number of nodes and arcs, and the delay is the time between the output of two consecutive solutions. To this aim, we give a characterization of the minimal s-d separators in a DAG through vertex cuts of an expanded version of the DAG itself. As a consequence of our main result, we provide an algorithm for enumerating all the minimal s-d cutsets in a temporal graph with delay O(m³), where m is the number of temporal arcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alessio Conte and Pierluigi Crescenzi and Andrea Marino and Giulia Punzi 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.25 urn:nbn:de:0030-drops-126932 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.25 eng https://creativecommons.org/licenses/by/3.0/legalcode