• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

Constructive algorithm for path-width of matroids

Jeong, Jisu; Kim, Eun Jung; Oum, Sang-il (2016), Constructive algorithm for path-width of matroids, in Krauthgamer, Robert, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, p. 1695-1704. 10.1137/1.9781611974331.ch116

Type
Communication / Conférence
External document link
https://arxiv.org/abs/1507.02184v1
Date
2016
Conference title
27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
Conference date
2016-01
Conference city
Arlington, Virginia
Conference country
United States
Book title
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
Book author
Krauthgamer, Robert
Publisher
Society for Industrial and Applied Mathematics
ISBN
978-1-61197-433-1
Number of pages
2106 (3 Vols)
Pages
1695-1704
Publication identifier
10.1137/1.9781611974331.ch116
Metadata
Show full item record
Author(s)
Jeong, Jisu
Department of Mathematical Sciences, KAIST
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Oum, Sang-il
Department of Mathematical Sciences, KAIST
Abstract (EN)
Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a linear layout V1, V2, …, Vn of the subspaces such that dim((V1 + V2 + ⃛ + Vi)∩(Vi+1 + ⃛ + Vn)) ≤ k for all i; such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the path-width of an F-represented matroid in matroid theory and computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory.We present a fixed-parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over F. As corollaries, we obtain a fixed-parameter tractable algorithm to produce a path-decomposition of width at most k for an input F-represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously. Our approach is based on dynamic programming combined with the idea developed by Bodlaender and Kloks (1996) for their work on path-width and tree-width of graphs.It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width; a theorem by Geelen, Gerards, and Whittle (2002) implies that for each fixed finite field F, there are finitely many forbidden F-representable minors for the class of matroids of path-width at most k. An algorithm by Hliněný (2006) can detect a minor in an input F-represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition even if the complete list of forbidden minors were known. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.
Subjects / Keywords
algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    An FPT 2-Approximation for Tree-Cut Decomposition 
    Kim, Eun Jung; Oum, Sang-il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2018) Article accepté pour publication ou publié
  • Thumbnail
    An FPT 2-Approximation for Tree-cut Decomposition 
    Kim, Eun Jung; Oum, Sang-Il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2015) Communication / Conférence
  • Thumbnail
    Twin-width VI: the lens of contraction sequences 
    Bonnet, Edouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan (2022) Communication / Conférence
  • Thumbnail
    On the tree-width of even-hole-free graphs 
    Aboulker, Pierre; Adler, Isolde; Kim, Eun Jung; Sintiari, Ni Luh Dewi; Trotignon, Nicolas (2021) Document de travail / Working paper
  • Thumbnail
    A polynomial-time algorithm for Outerplanar Diameter Improvement 
    Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo