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

DOI10.1137/1.9781611973402.10zbMath1421.68077arXiv1304.4626OpenAlexW1565709240MaRDI QIDQ5383969

Saket Saurabh, Daniel Lokshtanov, Fedor V. Fomin

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.4626

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (38)

A randomized algorithm for long directed cycle ⋮ Spotting Trees with Few Leaves ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Spotting Trees with Few Leaves ⋮ Deterministic Truncation of Linear Matroids ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ Unnamed Item ⋮ Deterministic parameterized algorithms for the graph motif problem ⋮ Parameterized approximation algorithms for packing problems ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ Unnamed Item ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Hitting forbidden subgraphs in graphs of bounded treewidth ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Parameterized algorithms for graph partitioning problems ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Representative families: a unified tradeoff-based approach ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Non-adaptive learning of a hidden hypergraph ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ Algebraic methods in the congested clique ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ Unnamed Item ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ Long directed \((s,t)\)-path: FPT algorithm ⋮ Unnamed Item ⋮ On the complexity of algorithms for detecting \(k\)-length negative cost cycles ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ Exact algorithms for intervalizing coloured graphs ⋮ Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter

This page was built for publication: Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms