Approximately counting locally-optimal structures
From MaRDI portal
Publication:295655
DOI10.1016/j.jcss.2016.04.001zbMath1342.68163OpenAlexW2149592811MaRDI QIDQ295655
John Lapinskas, Rob Gysel, Leslie Ann Goldberg
Publication date: 13 June 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2016.04.001
Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Counting minimal transversals of \(\beta\)-acyclic hypergraphs ⋮ Counting independent sets in cocomparability graphs ⋮ Approximation via Correlation Decay When Strong Spatial Mixing Fails
Cites Work
- Unnamed Item
- The graph formulation of the union-closed sets conjecture
- Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
- On the complexity of computing treelength
- How easy is local search?
- Efficient enumeration of all minimal separators in a graph
- Listing all potential maximal cliques of a graph
- Tree decompositions with small cost
- The relative complexity of approximate counting problems
- Treewidth computation and extremal combinatorics
- A revisit of the scheme for computing treewidth and minimum fill-in
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Graph Theory
- On exact algorithms for treewidth
- The Complexity of Approximately Counting Tree Homomorphisms
- Dominating Set Counting in Graph Classes
- Finding Induced Subgraphs via Minimal Triangulations
- Simple Local Search Problems that are Hard to Solve
- The Complexity of Ferromagnetic Ising with Local Fields
- Approximately Counting Locally-Optimal Structures
- Approximating the Partition Function of the Ferromagnetic Potts Model
- Exact Algorithms for Treewidth and Minimum Fill-In
- Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
- A New Algorithm for Generating All the Maximal Independent Sets
- Efficient Algorithms for Listing Combinatorial Structures
- Listing all Minimal Separators of a Graph
- Planar Graphs
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Minimal Triangulation Algorithms for Perfect Phylogeny Problems
- On Unapproximable Versions of $NP$-Complete Problems
