Compactors for parameterized counting problems

DOI10.1016/J.COSREV.2020.100344OpenAlexW3120337329MaRDI QIDQ826317FDOQ826317

Authors: Dimitrios M. Thilikos 

Publication date: 20 December 2021

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cosrev.2020.100344

Recommendations

• Counting problems in parameterized complexity
• The Parameterized Complexity of Counting Problems
• Parameterized counting problems
• scientific article; zbMATH DE number 1929968
• On the parameterized complexity of approximate counting
• On parameterized counting
• scientific article; zbMATH DE number 1979521
• Kernelizations for Parameterized Counting Problems
• Some hard families of parameterized counting problems
• scientific article; zbMATH DE number 3883612

zbMATH Keywords

graph algorithmsparameterized algorithmscompactorcounting algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A \(4k^2\) kernel for feedback vertex set
• Easy problems for tree-decomposable graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parameterized algorithms
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Vertex packings: Structural properties and algorithms
• Deciding first-order properties of nowhere dense graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Bidimensionality and kernels
• Improved upper bounds for vertex cover
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Nondeterminism within $P^ * $
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Linear kernels and single-exponential algorithms via protrusion decompositions
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Logic, graphs, and algorithms
• The structure of the models of decidable monadic theories of graphs
• The parameterised complexity of counting even and odd induced subgraphs
• The parameterised complexity of counting connected subgraphs and graph motifs
• Linearity of grid minors in treewidth with applications through bidimensionality
• On miniaturized problems in parameterized complexity theory
• Title not available (Why is that?)
• On the parameterized complexity of approximate counting
• Parameterized counting problems
• Title not available (Why is that?)
• Algorithms and Data Structures
• Kernelizations for Parameterized Counting Problems
• Efficient algorithms for counting parameterized list \(H\)-colorings
• Methods for algorithmic meta theorems
• Fixed-parameter tractability, definability, and model-checking
• Testing first-order properties for subclasses of sparse graphs
• (Meta) kernelization
• Title not available (Why is that?)
• Homomorphisms are a good basis for counting small subgraphs
• Title not available (Why is that?)
• Block interpolation: a framework for tight exponential-time counting complexity
• The restrictive \(H\)-coloring problem
• Complexity issues on bounded restrictive \(H\)-coloring
• Parameterized counting of trees, forests and matroid bases
• Graph minors and parameterized algorithm design
• Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
• Counting matchings with \(k\) unmatched vertices in planar graphs
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Kernelization. Theory of parameterized preprocessing
• Title not available (Why is that?)
• Weighted counting of \(k\)-matchings is \#W[1]-hard
• Title not available (Why is that?)
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Bidimensionality and parameterized algorithms (invited talk)
• Algorithms – ESA 2004

Cited In (1)

• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration

This page was built for publication: Compactors for parameterized counting problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q826317)