Parameterised Enumeration for Modification Problems

Downloadstatistik des Dokuments (Auswertung nach COUNTER):

Creignou, N.; Ktari, R.; Müller, J.-S.; Olive, F.; Vollmer, H.: Parameterised Enumeration for Modification Problems. In: Algorithms 12 (2019), Nr. 9, 189. DOI: https://doi.org/10.3390/a12090189

Version im Repositorium

Zum Zitieren der Version im Repositorium verwenden Sie bitte diesen DOI: https://doi.org/10.15488/10960

Zeitraum, für den die Download-Zahlen angezeigt werden:

Jahr: 
Monat: 

Summe der Downloads: 47




Kleine Vorschau
Zusammenfassung: 
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.
Lizenzbestimmungen: CC BY 4.0 Unported
Publikationstyp: Article
Publikationsstatus: publishedVersion
Erstveröffentlichung: 2019
Die Publikation erscheint in Sammlung(en):Fakultät für Elektrotechnik und Informatik

Verteilung der Downloads über den gewählten Zeitraum:

Herkunft der Downloads nach Ländern:

Pos. Land Downloads
Anzahl Proz.
1 image of flag of Germany Germany 19 40,43%
2 image of flag of United States United States 17 36,17%
3 image of flag of China China 6 12,77%
4 image of flag of Taiwan Taiwan 1 2,13%
5 image of flag of Singapore Singapore 1 2,13%
6 image of flag of Sweden Sweden 1 2,13%
7 image of flag of Iran, Islamic Republic of Iran, Islamic Republic of 1 2,13%
8 image of flag of France France 1 2,13%

Weitere Download-Zahlen und Ranglisten:


Hinweis

Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.