Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875760 | Theoretical Computer Science | 2017 | 17 Pages |
Abstract
We generalize these ideas to bigger graph classes. We introduce a new width parameter sim-width, of stronger modeling power than mim-width, by making a small change in the definition of mim-width. We prove that chordal graphs and co-comparability graphs have sim-width at most 1. We investigate a way to bound mim-width for graphs of bounded sim-width by excluding KtâKt and KtâSt as induced minors or induced subgraphs, and give algorithmic consequences. Lastly, we show that circle graphs have unbounded sim-width, and thus also unbounded mim-width.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dong Yeap Kang, O-joung Kwon, Torstein J.F. Strømme, Jan Arne Telle,