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
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
Department of Computer Science, University of Toronto, Canada.ORCID iD: 0000-0001-8217-0158
Department of Computer Science, University of Toronto, Canada.
Department of Computer Science, University of Toronto, Canada.
2012 (English)In: International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012, 13-24 p.Conference paper, Published paper (Refereed)
Abstract [en]

We study the approximability of a number of graph problems: treewidth and pathwidth of graphs, one-shot black (and black-white) pebbling costs of directed acyclic graphs, and a variety of different graph layout problems such as minimum cut linear arrangement and interval graph completion. We show that, assuming the recently introduced Small Set Expansion Conjecture, all of these problems are hard to approximate within any constant factor.

Place, publisher, year, edition, pages
2012. 13-24 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-112871DOI: 10.1007/978-3-642-32512-0_2Scopus ID: 2-s2.0-84865297320OAI: oai:DiVA.org:kth-112871DiVA: diva2:587539
Conference
15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012; Cambridge, MA; United States
Note

QC 20130523

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2016-04-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Austrin, Per

Search in DiVA

By author/editor
Austrin, Per
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 63 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