Article ID Journal Published Year Pages File Type
6875760 Theoretical Computer Science 2017 17 Pages PDF
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
, , , ,