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 (2)
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
This page was built for publication:
