A Note on Exponential-Time Algorithms for Linearwidth

2020/10/05 by Kobayashi, Yasuaki, Nakahata, Yu
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2010.02388

Abstract

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

Related

• A Single-Exponential Time 2-Approximation Algorithm for Treewidth
• A simple linear-time algorithm for finding path-decompositions of small width
• Tight Lower Bounds for Problems Parameterized by Rank-width
• An Improved Parameterized Algorithm for Treewidth
• A O(c^k n) 5-Approximation Algorithm for Treewidth