Compactors for parameterized counting problems

DOI10.1016/j.cosrev.2020.100344OpenAlexW3120337329MaRDI QIDQ826317

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

zbMATH Keywords

graph algorithmsparameterized algorithmscompactorcounting algorithms

Mathematics Subject Classification ID

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

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Improved upper bounds for vertex cover
• The structure of the models of decidable monadic theories of graphs
• On miniaturized problems in parameterized complexity theory
• Efficient algorithms for counting parameterized list \(H\)-colorings
• Linearity of grid minors in treewidth with applications through bidimensionality
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Block interpolation: a framework for tight exponential-time counting complexity
• The parameterised complexity of counting even and odd induced subgraphs
• The restrictive \(H\)-coloring problem
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• The parameterised complexity of counting connected subgraphs and graph motifs
• Complexity issues on bounded restrictive \(H\)-coloring
• Parameterized counting of trees, forests and matroid bases
• Parameterized counting problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Graph Minors and Parameterized Algorithm Design
• (Meta) Kernelization
• Easy problems for tree-decomposable graphs
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Vertex packings: Structural properties and algorithms
• Nondeterminism within $P^ * $
• Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
• Deciding First-Order Properties of Nowhere Dense Graphs
• Kernelization
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Weighted Counting of k-Matchings Is #W[1-Hard]
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Homomorphisms are a good basis for counting small subgraphs
• On the parameterized complexity of approximate counting
• Bidimensionality and Parameterized Algorithms (Invited Talk)
• Algorithms and Data Structures
• Testing first-order properties for subclasses of sparse graphs
• Bidimensionality and Geometric Graphs
• Kernelizations for Parameterized Counting Problems
• Algorithms – ESA 2004
• Parameterized Algorithms

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