2008/01/01 by Petr Hliněný, Sang‐il Oum · 137 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #graph theory and CDMA systems #Interconnection Networks and Systems #Matroid #Mathematics #Combinatorics #Finite field #Decomposition #Rank (graph theory) #Discrete mathematics #Constant (computer programming) #Graph #Computer science
paper · doi:10.1137/070685920
published in SIAM Journal on Computing 38(3), 1012-1032 (Society for Industrial and Applied Mathematics)
openalex publication_date 2008/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
We present a new algorithm that can output the rank-decomposition of width at most k of a graph if such exists. For that we use an algorithm that, for an input matroid represented over a fixed finite field, outputs its branch-decomposition of width at most k if such exists. This algorithm works also for partitioned matroids. Both of these algorithms are fixed-parameter tractable, that is, they run in time O(n3) where n is the number of vertices / elements of the input, for each constant value of k and any fixed finite field. The previous best algorithm for construction of a branch-decomposition or a rank-decomposition of optimal width due to Oum and Seymour [J. Combin. Theory Ser. B, 97 (2007), pp. 385–393] is not fixed-parameter tractable.