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

2013/04/16 by Fedor V. Fomin, Daniel Lokshtanov, Fomin, Fedor V. +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization

paper · pdf · doi:10.48550/arxiv.1304.4626

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.

Cited by

• Weighted k-Path and Other Problems in Almost O^*(2^k) Deterministic Time via Dynamic Representative Sets

Related

• Representative Families: A Unified Tradeoff-Based Approach
• Tight Lower Bounds for Problems Parameterized by Rank-width
• Weighted k-Path and Other Problems in Almost O^*(2^k) Deterministic Time via Dynamic Representative Sets
• A Formal Analysis of Algorithms for Matroids and Greedoids
• Efficient parameterized algorithms on graphs with heterogeneous structure: Combining tree-depth and modular-width