Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2012-004 (June 13, 2012)

Linear Layouts in Submodular Systems
by Hiroshi Nagamochi

pdf File

Linear layout of graphs/digraphs is one of the classical and important optimization problems that have many practical applications.: Recently Tamaki proposed an $O(mn^{k+1})$-time and $O(n^k)$-space algorithm for testing whether the pathwidth (or vertex separation) of a given digraph with $n$ vertices and $m$ edges is at most $k$. In this paper, we show that linear layout of digraphs with an objective function such as cutwidth, minimum linear arrangement, vertex separation (or pathwidth) and sum cut can be formulated as a linear layout problem on a submodular system $(V,f)$ and then propose a simple framework of search tree algorithms for finding a linear layout (a sequence of $V$) with a bounded width that minimizes a given cost function.: According to our framework, we obtain an $O( k m n^{2k })$-time and $O(n+m)$-space algorithm for testing whether the pathwidth of a given digraph is at most $k$.