Details
| Original language | English |
|---|---|
| Article number | 9 |
| Pages (from-to) | 189 |
| Number of pages | 1 |
| Journal | Algorithms |
| Volume | 12 |
| Issue number | 9 |
| Early online date | 9 Sept 2019 |
| Publication status | Published - Sept 2019 |
Abstract
Recently, Creignou et al. (Theory Comput. Syst. 2017), introduced the class DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable parameterised enumeration problems. In this paper, we propose a framework for parameterised ordered enumeration and will show how to obtain enumeration algorithms running with an FPT delay in the context of general modification problems. We study these problems considering two different orders of solutions, namely, lexicographic order and order by size. Furthermore, we present two generic algorithmic strategies. The first one is based on the well-known principle of self-reducibility and is used in the context of lexicographic order. The second one shows that the existence of a neighbourhood structure among the solutions implies the existence of an algorithm running with FPT delay which outputs all solutions ordered non-decreasingly by their size.
Keywords
- Bounded search tree, Enumeration, Ordering, Parameterised complexity, Parameterised enumeration
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Mathematics(all)
- Numerical Analysis
- Computer Science(all)
- Computational Theory and Mathematics
- Mathematics(all)
- Computational Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Algorithms, Vol. 12, No. 9, 9, 09.2019, p. 189.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Parameterised Enumeration for Modification Problems
AU - Creignou, Nadia
AU - Ktari, Raïda
AU - Meier, Arne
AU - Müller, Julian Steffen
AU - Olive, Frédéric
AU - Vollmer, Heribert
N1 - Funding information: This research was funded by Deutsche Forschungsgemeinschaft (ME 4279/1-2) and the French Agence Nationale de la Recherche (AGGREG project reference ANR-14-CE25-0017). We thank the anonymous reviewers for their valuable feedback. This research was funded by Deutsche Forschungsgemeinschaft (ME 4279/1-2) and the French Agence Nationale de la Recherche (AGGREG project reference ANR-14-CE25-0017).
PY - 2019/9
Y1 - 2019/9
N2 - Recently, Creignou et al. (Theory Comput. Syst. 2017), introduced the class DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable parameterised enumeration problems. In this paper, we propose a framework for parameterised ordered enumeration and will show how to obtain enumeration algorithms running with an FPT delay in the context of general modification problems. We study these problems considering two different orders of solutions, namely, lexicographic order and order by size. Furthermore, we present two generic algorithmic strategies. The first one is based on the well-known principle of self-reducibility and is used in the context of lexicographic order. The second one shows that the existence of a neighbourhood structure among the solutions implies the existence of an algorithm running with FPT delay which outputs all solutions ordered non-decreasingly by their size.
AB - Recently, Creignou et al. (Theory Comput. Syst. 2017), introduced the class DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable parameterised enumeration problems. In this paper, we propose a framework for parameterised ordered enumeration and will show how to obtain enumeration algorithms running with an FPT delay in the context of general modification problems. We study these problems considering two different orders of solutions, namely, lexicographic order and order by size. Furthermore, we present two generic algorithmic strategies. The first one is based on the well-known principle of self-reducibility and is used in the context of lexicographic order. The second one shows that the existence of a neighbourhood structure among the solutions implies the existence of an algorithm running with FPT delay which outputs all solutions ordered non-decreasingly by their size.
KW - Bounded search tree
KW - Enumeration
KW - Ordering
KW - Parameterised complexity
KW - Parameterised enumeration
UR - http://www.scopus.com/inward/record.url?scp=85072769261&partnerID=8YFLogxK
U2 - 10.3390/a12090189
DO - 10.3390/a12090189
M3 - Article
AN - SCOPUS:85072769261
VL - 12
SP - 189
JO - Algorithms
JF - Algorithms
IS - 9
M1 - 9
ER -