View in EDS PDF Full Text

An exact algorithm for the minimum sum coloring problem on partially decomposable graphs.

Saved in:
Bibliographic Details
Title: An exact algorithm for the minimum sum coloring problem on partially decomposable graphs.
Authors: Tammal, Fatma1 (AUTHOR) ftammal@usthb.dz, Aïder, Méziane1,2 (AUTHOR)
Source: RAIRO: Operations Research (2804-7303). 2025, Vol. 59 Issue 6, p3621-3648. 28p.
Subjects: Graph coloring, Branch & bound algorithms, Deterministic algorithms, Graph theory, Mathematical optimization
Abstract: Given an undirected graph G, the Minimum Sum Coloring Problem (MSCP) asks to find a legal vertex coloring of G using natural numbers that minimizes the total sum of the colors. In this paper, we propose an exact approach for MSCP using the modular decomposition tree of G, where our optimal solution is obtained at the root by the end of the process. This approach, called Modular Decomposition for Sum Coloring (MDSC), arises from the observation that decomposing graph G into disjoint subgraphs requires a careful selection of at least one solution from each subgraph, contributing to the final optimal solution. The modular decomposition technique aids us in making these selections intelligently. As a result, the branch and bound process becomes more efficient, faster, and powerful for solving MSCP on partially decomposable graphs. Numerical experiments demonstrate this improvement on several large DIMACS, COLOR 2002–2004 challenge graphs, and our generated instances, each containing between 500 and 1500 vertices. [ABSTRACT FROM AUTHOR]
Copyright of RAIRO: Operations Research (2804-7303) is the property of EDP Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 191891834
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: An exact algorithm for the minimum sum coloring problem on partially decomposable graphs.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Tammal%2C+Fatma%22">Tammal, Fatma</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> ftammal@usthb.dz</i><br /><searchLink fieldCode="AR" term="%22Aïder%2C+Méziane%22">Aïder, Méziane</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22RAIRO%3A+Operations+Research+%282804-7303%29%22">RAIRO: Operations Research (2804-7303)</searchLink>. 2025, Vol. 59 Issue 6, p3621-3648. 28p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Graph+coloring%22">Graph coloring</searchLink><br /><searchLink fieldCode="DE" term="%22Branch+%26+bound+algorithms%22">Branch & bound algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Deterministic+algorithms%22">Deterministic algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Given an undirected graph G, the Minimum Sum Coloring Problem (MSCP) asks to find a legal vertex coloring of G using natural numbers that minimizes the total sum of the colors. In this paper, we propose an exact approach for MSCP using the modular decomposition tree of G, where our optimal solution is obtained at the root by the end of the process. This approach, called Modular Decomposition for Sum Coloring (MDSC), arises from the observation that decomposing graph G into disjoint subgraphs requires a careful selection of at least one solution from each subgraph, contributing to the final optimal solution. The modular decomposition technique aids us in making these selections intelligently. As a result, the branch and bound process becomes more efficient, faster, and powerful for solving MSCP on partially decomposable graphs. Numerical experiments demonstrate this improvement on several large DIMACS, COLOR 2002–2004 challenge graphs, and our generated instances, each containing between 500 and 1500 vertices. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of RAIRO: Operations Research (2804-7303) is the property of EDP Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=191891834
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1051/ro/2025140
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 28
        StartPage: 3621
    Subjects:
      – SubjectFull: Graph coloring
        Type: general
      – SubjectFull: Branch & bound algorithms
        Type: general
      – SubjectFull: Deterministic algorithms
        Type: general
      – SubjectFull: Graph theory
        Type: general
      – SubjectFull: Mathematical optimization
        Type: general
    Titles:
      – TitleFull: An exact algorithm for the minimum sum coloring problem on partially decomposable graphs.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Tammal, Fatma
      – PersonEntity:
          Name:
            NameFull: Aïder, Méziane
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 11
              Text: 2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 28047303
          Numbering:
            – Type: volume
              Value: 59
            – Type: issue
              Value: 6
          Titles:
            – TitleFull: RAIRO: Operations Research (2804-7303)
              Type: main
ResultId 1