Enumerating maximal independent sets with applications to graph colouring.

DOI10.1016/J.ORL.2004.03.002MaRDI QIDQ703280zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3763968 (Why is no real title available?)
• scientific article; zbMATH DE number 889953 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A note on the complexity of the chromatic number problem
• An algorithm for the chromatic number of a graph
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• On cliques in graphs
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• The Number of Maximal Independent Sets in Triangle-Free Graphs

Cited in

(42)

• 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
• scientific article; zbMATH DE number 1830756 (Why is no real title available?)
• 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
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• The parameterized complexity of maximality and minimality problems
• 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
• Algorithms for dominating clique problems
• Computing branchwidth via efficient triangulations and blocks
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Exponential-time quantum algorithms for graph coloring problems
• 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
• Minimal dominating sets in interval graphs and trees
• Branch and recharge: exact algorithms for generalized domination
• Trimmed Moebius inversion and graphs of bounded degree
• Trimmed Moebius inversion and graphs of bounded degree
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• When polynomial approximation meets exact computation
• Solving connected dominating set faster than \(2^n\)
• Exact algorithms for counting 3-colorings of graphs
• scientific article; zbMATH DE number 2119675 (Why is no real title available?)
• Decomposition of realizable fuzzy relations
• Faster graph coloring in polynomial space
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• 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
• Iterative compression and exact algorithms
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces

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)