Efficient computation of representative sets with applications in parameterized and exact algorithms
From MaRDI portal
Abstract: We give two algorithms computing representative families of linear and uniform matroids and demonstrate how to use representative families for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include - LONGEST DIRECTED CYCLE - MINIMUM EQUIVALENT GRAPH (MEG) - Algorithms on graphs of bounded treewidth -k-PATH, k-TREE, and more generally, k-SUBGRAPH ISOMORPHISM, where the k-vertex pattern graph is of constant treewidth.
Recommendations
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Representative families: a unified tradeoff-based approach
- Representative families: a unified tradeoff-based approach
- Representative sets of product families
- Quasipolynomial representation of transversal matroids with applications in parameterized complexity
Cited in
(47)- A randomized polynomial kernel for subset feedback vertex set
- Non-adaptive learning of a hidden hypergraph
- Long directed \((s,t)\)-path: FPT algorithm
- On the complexity of algorithms for detecting \(k\)-length negative cost cycles
- Parameterized complexity of conflict-free matchings and paths
- Faster deterministic parameterized algorithm for k-path
- Partitioning a graph into small pieces with applications to path transversal
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Exact algorithms for intervalizing coloured graphs
- Exact learning from an honest teacher that answers membership queries
- A randomized algorithm for long directed cycle
- Representative sets of product families
- Representative families: a unified tradeoff-based approach
- A shortcut to (sun)flowers: kernels in logarithmic space or linear time
- Linear Time Constructions of Some d-Restriction Problems
- scientific article; zbMATH DE number 6687769 (Why is no real title available?)
- Deterministic parameterized algorithms for the graph motif problem
- Parameterized approximation algorithms for packing problems
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Deterministic subgraph detection in broadcast CONGEST
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- Parameterized algorithms for non-separating trees and branchings in digraphs
- Spotting trees with few leaves
- scientific article; zbMATH DE number 16648 (Why is no real title available?)
- Representative families of product families
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Quasipolynomial representation of transversal matroids with applications in parameterized complexity
- Parameterized complexity of conflict-free matchings and paths
- scientific article; zbMATH DE number 7204399 (Why is no real title available?)
- Contraction-bidimensionality of geometric intersection graphs
- Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs
- Spotting trees with few leaves
- The \(k\)-distinct language: parameterized automata constructions
- Parameterized Counting and Cayley Graph Expanders
- Hitting long directed cycles is fixed-parameter tractable
- Satisfiability to coverage in presence of fairness, matroid, and global constraints
- Parameterized applications of symbolic differentiation of (totally) multilinear polynomials
- Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth
- Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
- Cuts in graphs with matroid constraints
- Contraction bidimensionality of geometric intersection graphs
- Representative families: a unified tradeoff-based approach
This page was built for publication: Efficient computation of representative sets with applications in parameterized and exact algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5383969)
