Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
City University, New York.
2008 (English)In: Algorithms And Computation, Proceedings, Springer Berlin/Heidelberg, 2008, 220-231 p.Conference paper, Published paper (Refereed)
Abstract [en]

We place our focus on the gap between treewidth’s success in producing fixed-parameter polynomial algorithms for hard graph problems, and specifically Hamiltonian CircuitandMax Cut , and the failure of its directed variants (directed tree-width [9], DAG-width [11] and kelly-width [8]) to replicate it in the realm of digraphs.We answer the question of why this gap exists by giving two hardness results: we show that Directed Hamiltonian CircuitisW [2]-hard when the parameter is the width of the input graph, for any of these widths, and that Max Di Cut remains NP-hard even when restricted to DAGs, which have the minimum possible width under all these definitions. Our results also apply to directed pathwidth. (Eligible for best student paper)

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2008. 220-231 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 5369
Keyword [en]
Treewidth, Digraph decompositions, Parameterized Complexity
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-58591DOI: 10.1007/978-3-540-92182-0_22ISI: 000264205500019ISBN: 978-3-540-92181-3 (print)OAI: oai:DiVA.org:kth-58591DiVA: diva2:473393
Conference
19th International Symposium on Algorithms and Computations (ISAAC 2008), Gold Coast, AUSTRALIA, DEC 15-17, 2008
Note
QC 20120109Available from: 2012-01-05 Created: 2012-01-05 Last updated: 2012-01-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lampis, Michael
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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