On approximation intractability of the path-distance-width problem

DOI10.1016/S0166-218X(00)00275-4zbMath0980.68086OpenAlexW1987097519WikidataQ126812371 ScholiaQ126812371MaRDI QIDQ5936467

Koichi Yamazaki

Publication date: 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00275-4

zbMATH Keywords

path-distance-width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Approximating the path-distance-width for AT-free graphs and graphs in related classes ⋮ Approximability of the Path-Distance-Width for AT-free Graphs

Cites Work

• Unnamed Item
• The complexity of finding uniform emulations on paths and ring networks
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems

This page was built for publication: On approximation intractability of the path-distance-width problem