Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
From MaRDI portal
Publication:3177805
DOI10.1145/2886094zbMath1410.05212OpenAlexW3139078859WikidataQ60488363 ScholiaQ60488363MaRDI QIDQ3177805
Fedor V. Fomin, Saket Saurabh, Daniel Lokshtanov, Fahad Panolan
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2886094
Related Items
A note on algebraic techniques for subgraph detection ⋮ Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ On Computing the Hamiltonian Index of Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Narrow sieves for parameterized paths and packings ⋮ A multivariate framework for weighted FPT algorithms ⋮ Evaluation and Enumeration Problems for Regular Path Queries ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ Gerrymandering on graphs: computational complexity and parameterized algorithms ⋮ Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Detours in directed graphs ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Unnamed Item ⋮ Balanced substructures in bicolored graphs ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Unnamed Item ⋮ On computing the Hamiltonian index of graphs ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ Path-contractions, edge deletions and connectivity preservation ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Going Far from Degeneracy ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Finding temporal paths under waiting time constraints ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Slightly Superexponential Parameterized Problems ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Unnamed Item ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Linear representation of transversal matroids and gammoids parameterized by rank ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ Long directed \((s,t)\)-path: FPT algorithm ⋮ Parameterized complexity of conflict-free set cover ⋮ Fast exact algorithms for survivable network design with uniform requirements ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms ⋮ A faster parameterized algorithm for temporal matching ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Decomposition of Map Graphs with Applications. ⋮ Editing to Connected F-Degree Graph ⋮ Two edge-disjoint paths with length constraints ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ Parameterized complexity of multi-node hubs ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Partial vertex cover on graphs of bounded degeneracy ⋮ Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
This page was built for publication: Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
