Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth

DOI10.1145/3186898zbMath1457.05110arXiv1511.01379OpenAlexW4230551286WikidataQ129724156 ScholiaQ129724156MaRDI QIDQ4554362

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

Publication date: 13 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.01379

zbMATH Keywords

treewidthGaussian eliminationmaximum matchingparameterized complexity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (18)

Minimum Cuts in Surface Graphs ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Eccentricity queries and beyond using hub labels ⋮ Data Reduction for Maximum Matching on Real-World Graphs ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ Tangle bases: Revisited ⋮ Computing maximum matchings in temporal graphs ⋮ The power of linear-time data reduction for maximum matching ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Unnamed Item ⋮ An improved parameterized algorithm for treewidth ⋮ Parameterized aspects of triangle enumeration ⋮ A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph ⋮ Temporal matching ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Parameterized complexity of diameter ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width

This page was built for publication: Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth