Data-compression for parametrized counting problems on sparse graphs
From MaRDI portal
Publication:5091010
DOI10.4230/LIPICS.ISAAC.2018.20MaRDI QIDQ5091010FDOQ5091010
Authors: Eun Jung Kim, Dimitrios M. Thilikos, Maria Serna 
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1809.08160
Recommendations
Cites Work
- Fundamentals of parameterized complexity
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- On problems without polynomial kernels
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Kernelization -- preprocessing with a guarantee
- Easy problems for tree-decomposable graphs
- Title not available (Why is that?)
- Parameterized algorithms
- Title not available (Why is that?)
- Kernelization Lower Bounds by Cross-Composition
- Bidimensionality and kernels
- Infeasibility of instance compression and succinct PCPs for NP
- New limits to classical and quantum instance compression
- Algorithmic Meta-theorems
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Monadic second-order evaluations on tree-decomposable graphs
- Title not available (Why is that?)
- Logic, graphs, and algorithms
- The structure of the models of decidable monadic theories of graphs
- Lower bounds for kernelizations and other preprocessing procedures
- Title not available (Why is that?)
- Reduction algorithms for graphs of small treewidth
- 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
- Generalized model-checking over locally tree-decomposable classes
- Testing first-order properties for subclasses of sparse graphs
- (Meta) kernelization
- Losing Treewidth by Separating Subsets
Cited In (6)
- Compactors for parameterized counting problems
- A Retrospective on (Meta) Kernelization
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- Faster parameterized algorithms for modification problems to minor-closed classes
- Sparse obstructions for minor-covering parameters
- Bidimensionality and kernels
This page was built for publication: Data-compression for parametrized counting problems on sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091010)
