ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Algorithms, Vol. 11, Pages 173: Inapproximability of Rank, Clique, Boolean, and Maximum Induced Matching-Widths under Small Set Expansion Hypothesis (2018)

Koichi Yamazaki

MDPI

In: Algorithms

add to mindlist on the mindlist

Details

Publication Date: 2018

Description: Wu et al. (2014) showed that under the small set expansion hypothesis (SSEH) there is no polynomial time approximation algorithm with any constant approximation factor for several graph width parameters, including tree-width, path-width, and cut-width (Wu et al. 2014). In this paper, we extend this line of research by exploring other graph width parameters: We obtain similar approximation hardness results under the SSEH for rank-width and maximum induced matching-width, while at the same time we show the approximation hardness of carving-width, clique-width, NLC-width, and boolean-width. We also give a simpler proof of the approximation hardness of tree-width, path-width, and cut-widththan that of Wu et al.

Electronic ISSN: 1999-4893

Topics: Computer Science

Published by MDPI

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit