Concepedia

Approximation Algorithms For Coloring

Approximation Algorithms for Coloring is an algorithmic framework in computational combinatorics that belongs to the class of heuristic methods for NP-hard graph problems and specifically addresses graph coloring by computing near-optimal colorings with provable performance guarantees relative to the chromatic number.

706

Publications

26.4K

Citations

1.1K

Authors

526

Institutions

Publications per year

2017–2026

70

Parents

Publications

706

Smallest-last ordering and clustering and graph coloring algorithms

David W. Matula, Leland L. Beck · Journal of the ACM · 1983 · 530 citations · Full text

, , +7

Approximate graph coloring by semidefinite programming

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

, , +16

A Determinant Formula for the Number of Ways of Coloring a Map

George D. Birkhoff · Annals of Mathematics · 1912 · 390 citations

, , +4

On a property of the class of n-colorable graphs

D Seinsche · Journal of Combinatorial Theory Series B · 1974 · 306 citations

, , +9

A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph

Mark Jerrum · Random Structures and Algorithms · 1995 · 296 citations

, , +12

1–5 of 706

Authors

1.1K

  1. AK
    Alexandr Kostochka

    University of Illinois Urbana-Champaign, United States

    14 publications · 520 citations

    13

    h-index

  2. AH
    Alain Hertz

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

    10 publications · 708 citations

    10

    h-index

  3. OV
    O. V. Borodin

    Sobolev Institute of Mathematics, Russia

    9 publications · 370 citations

    9

    h-index

  4. AR
    André Raspaud

    Laboratoire Bordelais de Recherche en Informatique, France

    9 publications · 244 citations

    9

    h-index

  5. XZ
    Xuding Zhu

    National Sun Yat-sen University, Taiwan

    9 publications · 419 citations

    9

    h-index

1–5 of 1.1K

Institutions

526

  1. Centre National de la Recherche Scientifique

    Paris, France

    20 h-index

    59 publications

    1.8K citations

  2. Tel Aviv University

    Tel Aviv, Israel

    16 h-index

    29 publications

    913 citations

  3. University of Illinois Urbana-Champaign

    Urbana, United States

    16 h-index

    28 publications

    932 citations

  4. Rutgers, The State University of New Jersey

    New Brunswick, United States

    15 h-index

    20 publications

    1.1K citations

  5. Zhejiang Normal University

    Jinhua, China

    14 h-index

    27 publications

    665 citations

  6. Sobolev Institute of Mathematics

    Novosibirsk, Russia

    14 h-index

    21 publications

    667 citations

  7. Shandong University

    Jinan, China

    13 h-index

    43 publications

    1.1K citations

  8. Université de Bordeaux

    Bordeaux, France

    13 h-index

    25 publications

    657 citations

1–8 of 526

Venues

  1. Discrete Mathematics

    114 publications · 3.6K citations

    31

    h-index

  2. Journal of Combinatorial Theory Series B

    46 publications · 2.3K citations

    28

    h-index

  3. Discrete Applied Mathematics

    63 publications · 2.1K citations

    25

    h-index

  4. Information Processing Letters

    25 publications · 1.2K citations

    18

    h-index

  5. COMBINATORICA

    25 publications · 1.1K citations

    17

    h-index

1–5