Concepedia

Graph Coloring Approximation

Graph Coloring Approximation is an approximation algorithm that belongs to the class of combinatorial optimization methods, specifically designed to assign colors to the vertices of a graph in a way that minimizes the number of colors used while ensuring no two adjacent vertices share the same color, distinguishing itself by providing near-optimal solutions to the NP-hard graph coloring problem within polynomial time.

444

Publications

20.3K

Citations

766

Authors

405

Institutions

Publications per year

2017–2026

49

Parents

Publications

444

Color-coding

Noga Alon, Raphael Yuster, Uri Zwick · Journal of the ACM · 1995 · 1K citations · Full text

, , +16

Using tabu search techniques for graph coloring

Alain Hertz, D. de Werra · Computing · 1987 · 660 citations · Full text

, , +9

A practical approach for routing and wavelength assignment in large wavelength-routed optical networks

Dhritiman Banerjee, Biswanath Mukherjee · IEEE Journal on Selected Areas in Communications · 1996 · 511 citations

, , +16

Approximate graph coloring by semidefinite programming

David R. Karger, Rajeev Motwani, Madhu Sudan · Journal of the ACM · 1998 · 429 citations

, , +16

Genetic and hybrid algorithms for graph coloring

Charles Fleurent, Jacques A. Ferland · Annals of Operations Research · 1996 · 307 citations

, , +11

1–5 of 444

Authors

766

  1. JH
    Jin‐Kao Hao

    Université d'Angers, France

    12 publications · 684 citations

    12

    h-index

  2. AK
    Alexandr Kostochka

    University of Illinois Urbana-Champaign, United States

    9 publications · 338 citations

    9

    h-index

  3. AH
    Alain Hertz

    École Polytechnique Fédérale de Lausanne, Switzerland

    9 publications · 1.4K citations

    9

    h-index

  4. VT
    Vangélis Th. Paschos

    Université Paris Dauphine-PSL, France

    7 publications · 138 citations

    7

    h-index

  5. NZ
    Nicolas Zufferey

    University of Geneva, Switzerland

    7 publications · 795 citations

    7

    h-index

1–5 of 766

Institutions

405

  1. Centre National de la Recherche Scientifique

    Paris, France

    15 h-index

    39 publications

    883 citations

  2. Université d'Angers

    Angers, France

    12 h-index

    27 publications

    1.5K citations

  3. University of Illinois Urbana-Champaign

    Urbana, United States

    12 h-index

    14 publications

    504 citations

  4. École Polytechnique Fédérale de Lausanne

    Lausanne, Switzerland

    12 h-index

    14 publications

    2.2K citations

  5. Massachusetts Institute of Technology

    Cambridge, United States

    11 h-index

    14 publications

    1.9K citations

  6. Tel Aviv University

    Tel Aviv, Israel

    11 h-index

    22 publications

    3.6K citations

  7. Rutgers, The State University of New Jersey

    New Brunswick, United States

    11 h-index

    14 publications

    642 citations

  8. Princeton University

    Princeton, United States

    10 h-index

    11 publications

    686 citations

1–8 of 405

Venues

  1. Discrete Mathematics

    43 publications · 1.3K citations

    21

    h-index

  2. Discrete Applied Mathematics

    46 publications · 1.3K citations

    21

    h-index

  3. Journal of Combinatorial Theory Series B

    19 publications · 622 citations

    16

    h-index

  4. Information Processing Letters

    23 publications · 886 citations

    16

    h-index

  5. Theoretical Computer Science

    19 publications · 575 citations

    15

    h-index

1–5