liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Paradigms for Parameterized Enumeration
Aix-Marseille Université, France.
Leibniz Universität, Hannover, Germany.
Leibniz Universität, Hannover, Germany.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Show others and affiliations
2013 (English)In: Mathematical Foundations of Computer Science 2013 / [ed] Krishnendu Chatterjee, Jirí Sgall, Springer Berlin/Heidelberg, 2013, 290-301 p.Conference paper, Published paper (Refereed)
Abstract [en]

The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First we define formally different notions of efficient enumeration in the context of parameterized complexity. Second we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013. 290-301 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 8087
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-102670DOI: 10.1007/978-3-642-40313-2_27ISBN: 978-3-642-40312-5 (print)ISBN: 978-3-642-40313-2 (print)OAI: oai:DiVA.org:liu-102670DiVA: diva2:680741
Conference
38th International Symposium on Mathematical Foundations of Computer Science (MFCS-2013), Klosterneuburg, Austria, August 26-30, 2013
Available from: 2013-12-18 Created: 2013-12-18 Last updated: 2014-01-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Schmidt, Johannes

Search in DiVA

By author/editor
Schmidt, Johannes
By organisation
Software and SystemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf