The Complexity of Enumeration and Reliability Problems
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Listing minimal edge-covers of intersecting families with applications to connectivity problems
- Compressing probabilistic Prolog programs
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Enumeration aspects of maximal cliques and bicliques
- A rigorous methodology for specification and verification of business processes
- The counting complexity of a simple scheduling problem
- On counting 3-D matchings of size \(k\)
- Flows with unit path capacities and related packing and covering problems
- Monomial bases for broken circuit complexes
- The computational complexity of maximization and integration
- The complexity of counting homeomorphs
- On some natural complete operators
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- The complexity of colouring problems on dense graphs
- An analysis of Monte Carlo algorithms for counting problems
- On the construction of parallel computers from various basis of Boolean functions
- Approximation to measurable functions and its relation to probabilistic computation
- Some observations on the connection between counting and recursion
- Enumerative techniques for solving some nonconvex global optimization problems
- Parallel computation with threshold functions
- An application of the planar separator theorem to counting problems
- Edge-packings of graphs and network reliability
- Lower bounds on two-terminal network reliability
- Approximate counting, uniform generation and rapidly mixing Markov chains
- A Bayesian approach to relevance in game playing
- Combinatorial problems over power sets
- Sulla complessita di alcuni problemi di conteggio
- On counting problems and the polynomial-time hierarchy
- Enumerating the cycles of a digraph: a new preprocessing strategy
- The complexity of controlled selection
- The complexity of computing the number of strings of given length in context-free languages
- The computational complexity of abduction
- Counting linear extensions
- Restricted relativizations of probabilistic polynomial time
- A note on bounding \(k\)-terminal reliability
- On integer points in polyhedra
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Polynomial-time compression
- A very hard log-space counting class
- The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
- A catalog of minimally nonideal matrices
- The computational complexity of knot and matroid polynomials
- The maximum clique problem
- Computational complexity of loss networks
- The complexity of computing maximal word functions
- Extending matchings in claw-free graphs
- Finding all the perfect matchings in bipartite graphs
- Counting trees in a graph is \(\# \text{P}\)-complete
- Simple characterizations of \(P(\# P)\) and complete problems
- On the equivalence in complexity among three computation problems on maximum number of edge-disjoint s-t paths in a probabilistic graph
- On closure properties of GapP
- Algorithms to count paths and cycles
- The complexities of the coefficients of the Tutte polynomial
- Querying disjunctive databases through nonmonotonic logics
- A short certificate of the number of universal optimal strategies for stopping simple stochastic games
- On the complexity of partially observed Markov decision processes
- Polynomial-time inference of all valid implications for Horn and related formulae
- Computing optimal assignments for residual network reliability
- Metafinite model theory
- Two-path subsets: Efficient counting and applications to performability analysis
- The complexity of the characteristic and the minimal polynomial.
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- Linear-time algorithms for computing the reliability of bipartite and (\(\# \leqslant 2\)) star distributed computing systems.
- The Go polynomials of a graph.
- Bicycle dimension and special points of the Tutte polynomial
- A second step towards complexity-theoretic analogs of Rice's Theorem
- Domination of cyclic monotone \((s,t)\)-graphs
- Some observations on holographic algorithms
- The fewest clues problem
- Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
- On blockwise symmetric matchgate signatures and higher domain \#CSP
- Simulating cardinal preferences in Boolean games: a proof technique
- The stochastic stability of decentralized matching on a graph
- Linear-time algorithms for counting independent sets in bipartite permutation graphs
- Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
- The computational complexity of QoS measures for orchestrations. The computational complexity of QoS measures
- Understanding the complexity of axiom pinpointing in lightweight description logics
- Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
- Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
- The complexity of Bayesian networks specified by propositional and relational languages
- Number of spanning trees of different products of complete and complete bipartite graphs
- Stochastic enumeration with importance sampling
- The query complexity of a permutation-based variant of mastermind
- An efficient algorithm for link prediction in temporal uncertain social networks
- Maximizing misinformation restriction within time and budget constraints
- Uniquely pressable graphs: characterization, enumeration, and recognition
- Towards fixed-parameter tractable algorithms for abstract argumentation
- On the generation of circuits and minimal forbidden sets
- Counting models for 2SAT and 3SAT formulae
- Closest paths in graph drawings under an elastic metric
- An analogue of Hoffman's circulation conditions for max-balanced flows
- Series-parallel posets and the Tutte polynomial
- Voronoi diagrams with barriers and on polyhedra for minimal path planning
- Enumerative counting is hard
- Randomised algorithms
- The complexity of computing the Tutte polynomial on transversal matroids
- Recognition and dualization of disguised bidual Horn functions.
- Tally NP sets and easy census functions.
- Unification algorithms cannot be combined in polynomial time.
- Quorum systems constructed from combinatorial designs
This page was built for publication: The Complexity of Enumeration and Reliability Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3853129)
