scientific article; zbMATH DE number 7378587
From MaRDI portal
Publication:5009461
DOI10.4230/LIPIcs.IPEC.2018.1MaRDI QIDQ5009461
Publication date: 4 August 2021
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Hamiltonian cyclesperfect matchingsparameterized complexitycounting complexitygraph motifsgraph minor theory
Related Items
Parameterised counting in logspace, On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
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
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- Algorithmic uses of the Feferman-Vaught theorem
- The complexity of computing the permanent
- Holographic algorithms: from art to science
- Generalized model-checking over locally tree-decomposable classes
- The complexity of counting homomorphisms seen from the other side
- Counting induced subgraphs: a topological approach to \#W[1-hardness]
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Linearity of grid minors in treewidth with applications through bidimensionality
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Approximating the permanent of graphs with large factors
- On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
- Graph minors. XVI: Excluding a non-planar graph
- Which problems have strongly exponential complexity?
- Block interpolation: a framework for tight exponential-time counting complexity
- The parameterised complexity of counting even and odd induced subgraphs
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
- The parameterised complexity of counting connected subgraphs and graph motifs
- Computational complexity of counting problems on 3-regular planar graphs
- Parameterized counting of trees, forests and matroid bases
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- Parametrized complexity theory.
- The rank of connection matrices and the dimension of graph algebras
- Tight lower bounds for certain parameterized NP-hard problems
- Parameterized counting problems
- The complexity of partition functions
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Some Hard Families of Parameterized Counting Problems
- Finding, Minimizing, and Counting Weighted Subgraphs
- An Effective Dichotomy for the Counting Constraint Satisfaction Problem
- Counting and Detecting Small Subgraphs via Equations
- The statistics of dimers on a lattice
- Connection Matrices and the Definability of Graph Parameters
- Balanced families of perfect hash functions and their applications
- The Complexity of Approximately Counting Tree Homomorphisms
- The complexity of approximating conservative counting CSPs.
- Invitation to Algorithmic Uses of Inclusion–Exclusion
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Computational Complexity of Holant Problems
- Polynomial-Time Approximation Algorithms for the Ising Model
- (Meta) Kernelization
- Easy problems for tree-decomposable graphs
- Understanding the Complexity of Induced Subgraph Isomorphisms
- Computing Graph Polynomials on Graphs of Bounded Clique-Width
- Holographic Algorithms
- On counting homomorphisms to directed acyclic graphs
- Set Partitioning via Inclusion-Exclusion
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Balanced Hashing, Color Coding and Approximate Counting
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Color-coding
- Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time
- Fast Hamiltonicity Checking Via Bases of Perfect Matchings
- Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
- A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
- Fine-grained dichotomies for the Tutte plane and Boolean #CSP
- Complexity of Counting CSP with Complex Weights
- The Parameterized Complexity of Counting Problems
- Weighted Counting of k-Matchings Is #W[1-Hard]
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Homomorphisms are a good basis for counting small subgraphs
- Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
- Extensor-coding
- Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Dimer problem in statistical mechanics-an exact result
- The complexity of the counting constraint satisfaction problem
- Determinant Sums for Undirected Hamiltonicity
- Kernelizations for Parameterized Counting Problems
- Parameterized Algorithms
- Operations with structures
- A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
