Enumerating maximal independent sets with applications to graph colouring.

DOI10.1016/J.ORL.2004.03.002zbMATH Open1052.05055OpenAlexW2122639972WikidataQ56269085 ScholiaQ56269085MaRDI QIDQ703280FDOQ703280

Authors: 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

Recommendations

• scientific article; zbMATH DE number 1830756
• On the number of maximal independent sets in a graph
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• Faster graph coloring in polynomial space
• scientific article; zbMATH DE number 867639

zbMATH Keywords

Graph algorithmsChromatic numberExtremal graphsGraph colouringMaximal independent set

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A New Algorithm for Generating All the Maximal Independent Sets
• On cliques in graphs
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• A note on the complexity of the chromatic number problem
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• Title not available (Why is that?)
• An algorithm for the chromatic number of a graph
• Title not available (Why is that?)

Cited In (43)

• An algorithm for exact satisfiability analysed with the number of clauses as parameter
• Enumerating Minimal Dominating Sets in Triangle-Free Graphs
• Maximum independent sets partition of \((n, k)\)-star graphs
• Title not available (Why is that?)
• Approximation of min coloring by moderately exponential algorithms
• Exact algorithms for exact satisfiability and number of perfect matchings
• Counting and enumerating independent sets with applications to combinatorial optimization problems
• The parameterized complexity of maximality and minimality problems
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Fibonacci index and stability number of graphs: a polyhedral study
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• On two techniques of combining branching and treewidth
• Exponential-time quantum algorithms for graph coloring problems
• Algorithms for dominating clique problems
• Computing branchwidth via efficient triangulations and blocks
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Vertex coloring of a graph for memory constrained scenarios
• Independent sets in graphs
• Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
• On the computation of fixed points in Boolean networks
• Regular inference as vertex coloring
• Feedback vertex sets in tournaments
• Maximal induced matchings in \(K_4\)-free and \(K_5\)-free graphs
• Maximal induced matchings in triangle-free graphs
• Minimal dominating sets in interval graphs and trees
• Trimmed Moebius inversion and graphs of bounded degree
• Branch and recharge: exact algorithms for generalized domination
• When polynomial approximation meets exact computation
• Trimmed Moebius inversion and graphs of bounded degree
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Solving connected dominating set faster than \(2^n\)
• Title not available (Why is that?)
• Exact algorithms for counting 3-colorings of graphs
• Faster graph coloring in polynomial space
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• Decomposition of realizable fuzzy relations
• Iterative Compression and Exact Algorithms
• Turán Graphs, Stability Number, and Fibonacci Index
• When polynomial approximation meets exact computation
• Moderately exponential time and fixed parameter approximation algorithms
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
• Iterative compression and exact algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703280)