Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
From MaRDI portal
Publication:4554362
DOI10.1145/3186898zbMath1457.05110arXiv1511.01379OpenAlexW4230551286MaRDI 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
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (17)
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 ⋮ 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
