Small Maximal Independent Sets and Faster Exact Graph Coloring
From MaRDI portal
Publication:4435347
DOI10.7155/jgaa.00064zbMath1027.05092arXivcs/0011009OpenAlexW2124240997WikidataQ59409897 ScholiaQ59409897MaRDI QIDQ4435347
Publication date: 30 November 2003
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0011009
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Collective dynamics of phase-repulsive oscillators solves graph coloring problem, On the hardness of inclusion-wise minimal separators enumeration, Feedback Vertex Sets in Tournaments, Branch and recharge: exact algorithms for generalized domination, New plain-exponential time classes for graph homomorphism, Trimmed Moebius inversion and graphs of bounded degree, Determining the \(L(2,1)\)-span in polynomial space, The parameterized complexity of maximality and minimality problems, Exact algorithms for exact satisfiability and number of perfect matchings, Enumerating maximal independent sets with applications to graph colouring., On the number of maximal bipartite subgraphs of a graph, Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7, Facility location with tree topology and radial distance constraints, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Faster graph coloring in polynomial space, New Plain-Exponential Time Classes for Graph Homomorphism, Graph coloring by multiagent fusion search, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Exact algorithms for counting 3-colorings of graphs
