combinatorial algorithms – Optimization Online

A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting

Published: 2026/07/13

Combinatorial Optimization, Semi-definite Programming combinatorial algorithms, perfect graphs, semidefinite programming

We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perfect graph contains a clique of a given size by iteratively counting walks in the graph with certain weights assigned to its edges and nonedges. These weights are initialized according … Read more

Expert-Enhanced Machine Learning for Cardiac Arrhythmia Classification

Published: 2019/10/10, Updated: 2020/11/15

Biomedical Applications, Combinatorial Optimization combinatorial algorithms, decision support, healthcare, machine learning, mixed-integer nonlinear programming, optimization

We propose a new method for the classification task of distinguishing atrial Fibrillation (AFib) from regular atrial tachycardias including atrial Flutter (AFlu) on the basis of a surface electrocardiogram (ECG). Although recently many approaches for an automatic classification of cardiac arrhythmia were proposed, to our knowledge none of them can distinguish between these two. We … Read more