Fully polynomial-time parameterized computations for graphs and matrices of low treewidth

DOI10.1137/1.9781611974782.92MaRDI QIDQ4575835zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Marcin Wrochna

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.92

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Bounded treewidth and space-efficient linear algebra
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Algebraic Graph Algorithms
• On the power of tree-depth for fully polynomial FPT algorithms

Cited in

(13)

• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• A linear-time parameterized algorithm for computing the width of a DAG
• Bounded treewidth and space-efficient linear algebra
• On the power of tree-depth for fully polynomial FPT algorithms
• The parameterised complexity of list problems on graphs of bounded treewidth
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Revisiting decomposition by clique separators
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• The \(b\)-matching problem in distance-hereditary graphs and beyond
• The Power of Linear-Time Data Reduction for Maximum Matching
• A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Solving systems of linear equations through zero forcing set

This page was built for publication: Fully polynomial-time parameterized computations for graphs and matrices of low treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575835)