# Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms

arXiv: https://arxiv.org/abs/1304.4626 · HTML: https://mlsanity.com/paper/1304.4626/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2013.

## Built on by (most cited first, 1 of 1)

- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)

## Abstract (arXiv)

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.