Skip to content

phabi.ch

yet another source of inspiration…

  • contact

Tag: integer linear programming

Vertex Coloring using ILP

Posted on 7. August 20237. August 2023 by Fabian Leuthold

In this post I’ll show you how to solve the vertex coloring problem to optimality using linear programming. Since the problem is NP-complete, there is no algorithm which can solve any problem instance in deterministic polynomial time. In a former post, I used constraint programming to find an optimal (minimal) vertex coloring. A popular greedy… Read more Vertex Coloring using ILP

Skip to footer

what you can find here

posts on operations research, programming, tinkering, languages, health, society and more…

Categories

  • arduino
  • common
  • fun
  • heuristics & algorithms
  • micro:bit
  • music
  • optimization
  • programming
  • raspberry pi
  • tinkering
  • tools

Recent Posts

  • Vertex Coloring using ILP
  • micro:bit plays Bach
  • The Tennis Court Problem (TCP)
  • Solving Happy CubesĀ® on A micro:bit
  • Map Coloring Problem
Proudly powered by WordPress | Theme: Yocto by Humble Themes.