Approximately counting locally-optimal structures

DOI10.1016/J.JCSS.2016.04.001MaRDI QIDQ295655zbMATH OpenOpenAlexFDO

Authors Leslie Ann Goldberg, Rob Gysel, John Lapinskas

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

zbMATH Keywords

complexityapproximate countingbipartite graphsmaximal independent setsminimal separators

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Recommendations

• Approximately Counting Locally-Optimal Structures
• A fixed-parameter perspective on \#BIS
• A fixed-parameter perspective on \#BIS
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• \#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Cites work

• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A revisit of the scheme for computing treewidth and minimum fill-in
• Approximately Counting Locally-Optimal Structures
• Dominating Set Counting in Graph Classes
• Efficient Algorithms for Listing Combinatorial Structures
• Efficient enumeration of all minimal separators in a graph
• Exact Algorithms for Treewidth and Minimum Fill-In
• Finding induced subgraphs via minimal triangulations
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
• Graph theory
• How easy is local search?
• Listing all Minimal Separators of a Graph
• Listing all potential maximal cliques of a graph
• Minimal Triangulation Algorithms for Perfect Phylogeny Problems
• On Unapproximable Versions of $NP$-Complete Problems
• On exact algorithms for treewidth
• On the complexity of computing treelength
• Planar Graphs
• Simple Local Search Problems that are Hard to Solve
• Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
• The Complexity of Ferromagnetic Ising with Local Fields
• The complexity of approximately counting tree homomorphisms
• The complexity of counting in sparse, regular, and planar graphs
• The relative complexity of approximate counting problems
• Tree decompositions with small cost
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth computation and extremal combinatorics

Cited in

(5)

• scientific article; zbMATH DE number 1453077 (Why is no real title available?)
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Counting minimal transversals of -acyclic hypergraphs
• Approximately Counting Locally-Optimal Structures
• Counting independent sets in cocomparability graphs

This page was built for publication: Approximately counting locally-optimal structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q295655)