Approximately Counting Locally-Optimal Structures

DOI10.1007/978-3-662-47672-7_53zbMath1440.68118arXiv1411.6829OpenAlexW2570129681MaRDI QIDQ3448823

Rob Gysel, John Lapinskas, Leslie Ann Goldberg

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.6829

Mathematics Subject Classification ID

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 (4)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ Approximately counting locally-optimal structures ⋮ Counting Homomorphisms to Square-Free Graphs, Modulo 2 ⋮ Approximately Counting Locally-Optimal Structures

Cites Work

• 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
• On exact algorithms for treewidth
• 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
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Minimal Triangulation Algorithms for Perfect Phylogeny Problems
• On Unapproximable Versions of $NP$-Complete Problems

This page was built for publication: Approximately Counting Locally-Optimal Structures