A General Framework for Enumerating Equivalence Classes of Solutions
| Autor: | Yishu Wang, Arnaud Mary, Marie-France Sagot, Blerina Sinaimeri |
|---|---|
| Přispěvatelé: | Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS), Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
J.3 General Computer Science F.2 Applied Mathematics Enumeration algorithm Enumeration algorithms Equivalence relation Dynamic programming Dynamic programming Computer Science Applications Mathematics of computing → Graph enumeration 68W40 68Q25 68R99 Equivalence relation Computer Science - Data Structures and Algorithms Dynamic programming Enumeration algorithms Equivalence relation Theory of computation → Dynamic programming Data Structures and Algorithms (cs.DS) [INFO]Computer Science [cs] Enumeration algorithms Theory of computation → Backtracking |
| Zdroj: | ESA 2021-29th Annual European Symposium on Algorithms ESA 2021-29th Annual European Symposium on Algorithms, Sep 2021, Virtual, Portugal. pp.1-14, ⟨10.4230/LIPIcs.ESA.2021.80⟩ |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-023-01131-1 |
| Popis: | 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. 36 pages, 8 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink