DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.38

On Constrained Intersection Representations of Graphs and Digraphs

Authors: Ferdinando Cicalese, Clément Dallard, and Martin Milanič

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract

We study the problem of determining minimal directed intersection representations of DAGs in a model introduced by [Kostochka, Liu, Machado, and Milenkovic, ISIT2019]: vertices are assigned color sets, two vertices are connected by an arc if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head, and the goal is to minimize the total number of colors. We show that the problem is polynomially solvable in the class of triangle-free and Hamiltonian DAGs and also disclose the relationship of this problem with several other models of intersection representations of graphs and digraphs.

Cite as

Ferdinando Cicalese, Clément Dallard, and Martin Milanič. On Constrained Intersection Representations of Graphs and Digraphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cicalese_et_al:LIPIcs.ISAAC.2022.38,
  author =	{Cicalese, Ferdinando and Dallard, Cl\'{e}ment and Milani\v{c}, Martin},
  title =	{{On Constrained Intersection Representations of Graphs and Digraphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.38},
  URN =		{urn:nbn:de:0030-drops-173239},
  doi =		{10.4230/LIPIcs.ISAAC.2022.38},
  annote =	{Keywords: Directed intersection representation, intersection number}
}

Document

DOI: 10.4230/DagSemProc.09281.1

09281 Abstracts Collection – Search Methodologies

Authors: Rudolf Ahlswede, Ferdinando Cicalese, and Ugo Vaccaro

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

From 05.07.09 to 10.07.09, the Dagstuhl Seminar 09281 on ``Search Methodologies '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. Abstracts of the presentations given during the seminar are put together in this paper. The first section describes the seminar topics and goals in general. We also briefly comment on how the topics were addressed in the talks. Links to extended abstracts or full papers are provided, if available.

Cite as

Rudolf Ahlswede, Ferdinando Cicalese, and Ugo Vaccaro. 09281 Abstracts Collection – Search Methodologies. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ahlswede_et_al:DagSemProc.09281.1,
  author =	{Ahlswede, Rudolf and Cicalese, Ferdinando and Vaccaro, Ugo},
  title =	{{09281 Abstracts Collection – Search Methodologies}},
  booktitle =	{Search Methodologies},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.1},
  URN =		{urn:nbn:de:0030-drops-22457},
  doi =		{10.4230/DagSemProc.09281.1},
  annote =	{Keywords: Search algorithms, group testing, fault-tolerance, identification, decision tree, multi-access communication}
}

Search Results

Documents authored by Cicalese, Ferdinando

On Constrained Intersection Representations of Graphs and Digraphs

Abstract

Cite as

09281 Abstracts Collection – Search Methodologies

Abstract

Cite as

Thanks for your feedback!

Could not send message