Search Results

Documents authored by Sagot, Marie-France

Document
DOI: 10.4230/LIPIcs.ESA.2021.80
A General Framework for Enumerating Equivalence Classes of Solutions

Authors: Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of contexts, including optimization ones that can be addressed by dynamic programming algorithms, and for certain types of equivalence relations between solutions.
Cite as

Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri. A General Framework for Enumerating Equivalence Classes of Solutions. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ESA.2021.80,
  author =	{Wang, Yishu and Mary, Arnaud and Sagot, Marie-France and Sinaimeri, Blerina},
  title =	{{A General Framework for Enumerating Equivalence Classes of Solutions}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.80},
  URN =		{urn:nbn:de:0030-drops-146614},
  doi =		{10.4230/LIPIcs.ESA.2021.80},
  annote =	{Keywords: Enumeration algorithms, Equivalence relation, Dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.WABI.2021.3
Making Sense of a Cophylogeny Output: Efficient Listing of Representative Reconciliations

Authors: Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri

Published in: LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)

Abstract
Cophylogeny reconciliation is a powerful method for analyzing host-parasite (or host-symbiont) co-evolution. It models co-evolution as an optimization problem where the set of all optimal solutions may represent different biological scenarios which thus need to be analyzed separately. Despite the significant research done in the area, few approaches have addressed the problem of helping the biologist deal with the often huge space of optimal solutions. In this paper, we propose a new approach to tackle this problem. We introduce three different criteria under which two solutions may be considered biologically equivalent, and then we propose polynomial-delay algorithms that enumerate only one representative per equivalence class (without listing all the solutions). Our results are of both theoretical and practical importance. Indeed, as shown by the experiments, we are able to significantly reduce the space of optimal solutions while still maintaining important biological information about the whole space.
Cite as

Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri. Making Sense of a Cophylogeny Output: Efficient Listing of Representative Reconciliations. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.WABI.2021.3,
  author =	{Wang, Yishu and Mary, Arnaud and Sagot, Marie-France and Sinaimeri, Blerina},
  title =	{{Making Sense of a Cophylogeny Output: Efficient Listing of Representative Reconciliations}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.3},
  URN =		{urn:nbn:de:0030-drops-143564},
  doi =		{10.4230/LIPIcs.WABI.2021.3},
  annote =	{Keywords: Cophylogeny, Enumeration, Equivalence relation, Dynamic programming}
}
Document
DOI: 10.4230/DagRep.8.10.63
Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative (Dagstuhl Seminar 18421)

Authors: Henning Fernau, Petr. A. Golovach, and Marie-France Sagot

Published in: Dagstuhl Reports, Volume 8, Issue 10 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18421 "Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative". Enumeration problems require to list all wanted objects of the input as, e.g., particular subsets of the vertex or edge set of a given graph or particular satisfying assignments of logical expressions. Enumeration problems arise in a natural way in various fields of Computer Science, as, e.g., Artificial Intelligence and Data Mining, in Natural Sciences Engineering, Social Sciences, and Biology. The main challenge of the area of enumeration problems is that, contrary to decision, optimization and even counting problems, the output length of an enumeration problem is often exponential in the size of the input and cannot be neglected. This makes enumeration problems more challenging than many other types of algorithmic problems and demands development of specific techniques. The principal goals of our Dagstuhl seminar were to increase the visibility of algorithmic enumeration within (Theoretical) Computer Science and to contribute to establishing it as an area of ``Algorithms and Complexity''. The seminar brought together researchers within the algorithms community, other fields of Computer Science and Computer Engineering, as well as researchers working on enumeration problems in other application areas, in particular Biology. The aim was to accelerate developments and discus new directions including algorithmic tools and hardness proofs.
Cite as

Henning Fernau, Petr. A. Golovach, and Marie-France Sagot. Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative (Dagstuhl Seminar 18421). In Dagstuhl Reports, Volume 8, Issue 10, pp. 63-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{fernau_et_al:DagRep.8.10.63,
  author =	{Fernau, Henning and Golovach, Petr. A. and Sagot, Marie-France},
  title =	{{Algorithmic Enumeration: Output-sensitive, Input-Sensitive, Parameterized, Approximative (Dagstuhl Seminar 18421)}},
  pages =	{63--86},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{10},
  editor =	{Fernau, Henning and Golovach, Petr. A. and Sagot, Marie-France},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.10.63},
  URN =		{urn:nbn:de:0030-drops-103483},
  doi =		{10.4230/DagRep.8.10.63},
  annote =	{Keywords: algorithms, input-sensitive enumeration, output-sensitive enumeration}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact