A Note on Exponential-Time Algorithms for Linearwidth

10/05/2020

∙

by   Yasuaki Kobayashi, et al.

∙

0

∙

share

In this note, we give an algorithm that computes the linearwidth of input n-vertex graphs in time O^*(2^n), which improves a trivial O^*(2^m)-time algorithm, where n and m the number of vertices and edges, respectively.