Small Maximal Independent Sets and Faster Exact Graph Coloring

DOI10.7155/jgaa.00064zbMath1027.05092arXivcs/0011009WikidataQ59409897 ScholiaQ59409897MaRDI QIDQ4435347

David Eppstein

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

Mathematics Subject Classification ID

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, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Collective dynamics of phase-repulsive oscillators solves graph coloring problem, Faster graph coloring in polynomial space, 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, Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Exact algorithms for counting 3-colorings of graphs, Facility location with tree topology and radial distance constraints, 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