2 Search Results for "Marino, Daniel"


Document
Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs

Authors: Alessio Conte, Pierluigi Crescenzi, Andrea Marino, and Giulia Punzi

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
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.

Cite as

Alessio Conte, Pierluigi Crescenzi, Andrea Marino, and Giulia Punzi. Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{conte_et_al:LIPIcs.MFCS.2020.25,
  author =	{Conte, Alessio and Crescenzi, Pierluigi and Marino, Andrea and Punzi, Giulia},
  title =	{{Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.25},
  URN =		{urn:nbn:de:0030-drops-126932},
  doi =		{10.4230/LIPIcs.MFCS.2020.25},
  annote =	{Keywords: minimal cutset, temporal graph, minimal separator, directed acyclic graph}
}
Document
The Silently Shifting Semicolon

Authors: Daniel Marino, Todd Millstein, Madanlal Musuvathi, Satish Narayanasamy, and Abhayendra Singh

Published in: LIPIcs, Volume 32, 1st Summit on Advances in Programming Languages (SNAPL 2015)


Abstract
Memory consistency models for modern concurrent languages have largely been designed from a system-centric point of view that protects, at all costs, optimizations that were originally designed for sequential programs. The result is a situation that, when viewed from a programmer's standpoint, borders on absurd. We illustrate this unfortunate situation with a brief fable and then examine the opportunities to right our path.

Cite as

Daniel Marino, Todd Millstein, Madanlal Musuvathi, Satish Narayanasamy, and Abhayendra Singh. The Silently Shifting Semicolon. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 32, pp. 177-189, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{marino_et_al:LIPIcs.SNAPL.2015.177,
  author =	{Marino, Daniel and Millstein, Todd and Musuvathi, Madanlal and Narayanasamy, Satish and Singh, Abhayendra},
  title =	{{The Silently Shifting Semicolon}},
  booktitle =	{1st Summit on Advances in Programming Languages (SNAPL 2015)},
  pages =	{177--189},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-80-4},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{32},
  editor =	{Ball, Thomas and Bodík, Rastislav and Krishnamurthi, Shriram and Lerner, Benjamin S. and Morriset, Greg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2015.177},
  URN =		{urn:nbn:de:0030-drops-50259},
  doi =		{10.4230/LIPIcs.SNAPL.2015.177},
  annote =	{Keywords: memory consistency models; sequential consistency; safe programming languages; data races}
}
  • Refine by Author
  • 1 Conte, Alessio
  • 1 Crescenzi, Pierluigi
  • 1 Marino, Andrea
  • 1 Marino, Daniel
  • 1 Millstein, Todd
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 directed acyclic graph
  • 1 memory consistency models; sequential consistency; safe programming languages; data races
  • 1 minimal cutset
  • 1 minimal separator
  • 1 temporal graph

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail