Small Maximal Independent Sets and Faster Exact Graph Coloring
From MaRDI portal
Publication:4435347
DOI10.7155/jgaa.00064zbMath1027.05092arXivcs/0011009WikidataQ59409897 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
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
On the number of maximal bipartite subgraphs of a graph, Feedback Vertex Sets in Tournaments, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Branch and recharge: exact algorithms for generalized domination, New plain-exponential time classes for graph homomorphism, Enumerating maximal independent sets with applications to graph colouring., Exact algorithms for exact satisfiability and number of perfect matchings, Graph coloring by multiagent fusion search, 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, Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration, New Plain-Exponential Time Classes for Graph Homomorphism
