Small Maximal Independent Sets and Faster Exact Graph Coloring

DOI10.7155/JGAA.00064zbMath1027.05092arXivcs/0011009OpenAlexW2124240997WikidataQ59409897 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

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

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

This page was built for publication: Small Maximal Independent Sets and Faster Exact Graph Coloring