Change search
ReferencesLink to record
Permanent link

Direct link
Parameterized algorithms for modular-width
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2013 (English)In: Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, Springer, 2013, 163-176 p.Conference paper (Refereed)
Abstract [en]

It is known that a number of natural graph problems which are FPT parameterized by treewidth become W-hard when parameterized by clique-width. It is therefore desirable to find a different structural graph parameter which is as general as possible, covers dense graphs but does not incur such a heavy algorithmic penalty. The main contribution of this paper is to consider a parameter called modular-width, defined using the well-known notion of modular decompositions. Using a combination of ILP and dynamic programming we manage to design FPT algorithms for Coloring and Partitioning into paths (and hence Hamiltonian path and Hamiltonian cycle), which are W-hard for both clique-width and its recently introduced restriction, shrub-depth. We thus argue that modular-width occupies a sweet spot as a graph parameter, generalizing several simpler notions on dense graphs but still evading the "price of generality" paid by clique-width.

Place, publisher, year, edition, pages
Springer, 2013. 163-176 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 8246 LNCS
Keyword [en]
FPT algorithms, Graph parameters, Graph problems, Hamiltonian cycle, Hamiltonian path, Modular decomposition, Parameterized algorithm, Structural graph
National Category
Computer Science
URN: urn:nbn:se:kth:diva-143283DOI: 10.1007/978-3-319-03898-8_15ScopusID: 2-s2.0-84893094633ISBN: 978-331903897-1OAI: diva2:706378
8th International Symposium on Parameterized and Exact Computation, IPEC 2013; Sophia Antipolis; France; 4 September 2013 through 6 September 2013

QC 20140320

Available from: 2014-03-20 Created: 2014-03-19 Last updated: 2014-03-20Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Lampis, Michael
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 34 hits
ReferencesLink to record
Permanent link

Direct link