Enumerating maximal independent sets with applications to graph colouring.

DOI10.1016/J.ORL.2004.03.002zbMath1052.05055OpenAlexW2122639972WikidataQ56269085 ScholiaQ56269085MaRDI QIDQ703280

Jesper Makholm Byskov

Publication date: 11 January 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.03.002

zbMATH Keywords

Graph algorithmsChromatic numberExtremal graphsGraph colouringMaximal independent set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (36)

Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ Minimal dominating sets in interval graphs and trees ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Vertex coloring of a graph for memory constrained scenarios ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Feedback Vertex Sets in Tournaments ⋮ Branch and recharge: exact algorithms for generalized domination ⋮ Decomposition of realizable fuzzy relations ⋮ Trimmed Moebius inversion and graphs of bounded degree ⋮ Regular inference as vertex coloring ⋮ When polynomial approximation meets exact computation ⋮ Independent sets in graphs ⋮ The parameterized complexity of maximality and minimality problems ⋮ When polynomial approximation meets exact computation ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Algorithms for dominating clique problems ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Iterative compression and exact algorithms ⋮ Iterative Compression and Exact Algorithms ⋮ Approximation of min coloring by moderately exponential algorithms ⋮ On the computation of fixed points in Boolean networks ⋮ Maximal Induced Matchings in Triangle-Free Graphs ⋮ On two techniques of combining branching and treewidth ⋮ Faster graph coloring in polynomial space ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Fibonacci index and stability number of graphs: a polyhedral study ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ An algorithm for exact satisfiability analysed with the number of clauses as parameter ⋮ Turán Graphs, Stability Number, and Fibonacci Index ⋮ Exponential-time quantum algorithms for graph coloring problems ⋮ Moderately exponential time and fixed parameter approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the complexity of the chromatic number problem
• A New Algorithm for Generating All the Maximal Independent Sets
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• An algorithm for the chromatic number of a graph
• On cliques in graphs

This page was built for publication: Enumerating maximal independent sets with applications to graph colouring.