An Improved DSATUR‐Based Branch‐and‐Bound Algorithm for the Vertex Coloring Problem

No abstract is available for this paper.

• Publication year

  2017

• Venue

  Networks

• Publication date

  2017-01-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/net.21716
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Solving Vertex Coloring Problems as Maximum Weighted Stable Set Problems

  2017cited by this paper
• Lower Bounding Techniques for DSATUR-based Branch and Bound

  2016cited by this paper
• Computers And Intractability A Guide To The Theory Of Np Completeness

  2016influential reference
• A branch‐and‐price algorithm for the (k,c)‐coloring problem

  2015cited by this paper
• A review on algorithms for maximum clique problems

  2015cited by this paper
• Exploring the role of graph spectra in graph coloring algorithm performance

  2014cited by this paper
• A Wide Branching Strategy for the Graph Coloring Problem

  2014cited by this paper
• A DSATUR-based algorithm for the Equitable Coloring Problem

  2013cited by this paper
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

  2012cited by this paper
• Maximum-weight stable sets and safe lower bounds for graph coloring

  2012cited by this paper
• Localization and scheduling protocols for actor‐centric sensor networks

  2012cited by this paper
• A new DSATUR-based algorithm for exact vertex coloring

  2012influential reference
• An exact bit-parallel algorithm for the maximum clique problem

  2011cited by this paper
• An improved bit parallel exact maximum clique algorithm

  2011cited by this paper
• An exact approach for the Vertex Coloring Problem

  2011influential reference
• An Efficient Branch-and-Bound Algorithm Based on MaxSAT for the Maximum Clique Problem

  2010cited by this paper
• A survey on vertex coloring problems

  2010cited by this paper
• On the recursive largest first algorithm for graph colouring

  2008cited by this paper
• A cutting plane algorithm for graph coloring

  2008cited by this paper
• On a graph coloring problem arising from discrete tomography

  2008cited by this paper
• A one-to-one correspondence between colorings and stable sets

  2008influential reference
• Graph colouring approaches for a satellite range scheduling problem

  2008cited by this paper
• Techniques for analyzing dynamic random graph models of web‐like networks: An overview

  2008cited by this paper
• A Branch and Bound Algorithm for Matching Protein Structures

  2007cited by this paper
• A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding

  2007cited by this paper
• A Branch-and-Cut algorithm for graph coloring

  2006cited by this paper
• A server for automated performance analysis of benchmarking data

  2006cited by this paper
• On the asymmetric representatives formulation for the vertex coloring problem

  2005cited by this paper
• Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results

  2005cited by this paper
• Graph Coloring for Air Traffic Flow Management

  2004cited by this paper
• Selected Topics in Column Generation

  2002cited by this paper
• A fast algorithm for the maximum clique problem

  2002cited by this paper
• Solving the minimum‐weighted coloring problem

  2001cited by this paper
• Benchmarking optimization software with performance profiles

  2001cited by this paper
• Combinatorial optimization

  1997cited by this paper
• A Column Generation Approach for Graph Coloring

  1996influential reference
• An improved algorithm for exact graph coloring

  1993cited by this paper
• Combinatorial Optimization

  1992influential reference
• The priority-based coloring approach to register allocation

  1990cited by this paper
• I-Colorings, I-Phasings, and I-Intersection assignments for graphs, and their applications

  1983cited by this paper
• The ellipsoid method and its consequences in combinatorial optimization

  1981cited by this paper
• A Graph Coloring Algorithm for Large Scheduling Problems.

  1979cited by this paper
• New methods to color the vertices of a graph

  1979influential reference
• Upper Bounds on the Order of a Clique of a Graph

  1972cited by this paper
• ON EIGENVALUES AND COLORINGS OF GRAPHS, II

  1970cited by this paper

• A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs

  2025cites this paper
• A Hybrid Graph-Coloring and Metaheuristic Framework for Resource Allocation in Dynamic E-Health Wireless Sensor Networks

  2025cites this paper
• HyColor: An Efficient Heuristic Algorithm for Graph Coloring

  2025cites this paper
• A Customized SAT-based Solver for Graph Coloring

  2025cites this paper
• A Survey of Graph-Based Resource Management in Wireless Networks—Part I: Optimization Approaches

  2025cites this paper
• Optimality of DSatur algorithm on chordal graphs

  2024cites this paper
• Solving the List Coloring Problem through a Branch-and-Price algorithm

  2023cites this paper
• RESEARCH UNIT SELF-ASSESSMENT

  2023cites this paper
• Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring

  2023cites this paper
• Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022

  2022cites this paper
• Partitioning Geometric Graphs into Plane Subgraphs

  2022cites this paper
• Improving local search for the weighted sum coloring problem using the branch-and-bound algorithm

  2022cites this paper
• Local Search with Weighting Schemes for the CG: SHOP 2022 Competition (CG Challenge)

  2022cites this paper
• A Structure-Driven Genetic Algorithm for Graph Coloring

  2021cites this paper
• A Novel Algorithm for Vertex Sum Distinguishing Total Coloring Based on Multiobjective Optimization

  2021influential citation
• Vertex coloring approach for Q-coverage problem in wireless sensor network

  2021cites this paper
• Graph coloring with decision diagrams

  2021cites this paper
• Coverage and Connectivity-Based 3D Wireless Sensor Deployment Optimization

  2020cites this paper
• Optimizing Wireless Charger Placement for Rechargeable Wireless Sensors

  2018influential citation
• Optimality Clue for Graph Coloring Problem

  2018cites this paper
• Exact Algorithms for the Graph Coloring Problem

  2018influential citation
• Reformulations and Decompositions of Mixed Integer Linear and Nonlinear Programs

  2017cites this paper
• Exact algorithms for the Vertex Coloring Problem and its generalisations. (Résolution exacte du Problème de Coloration de Graphe et ses variantes)

  2017cites this paper
• Preface: Static and dynamic optimization models for network routing problems

  2017cites this paper
• Uncertain vertex coloring problem

  2017cites this paper