6 papers
SAT Encoding of Partial Ordering Models for Graph Coloring Problems
Daniel Faber, Adalat Jabrayilov, Petra Mutzel
In this paper, we suggest new SAT encodings of the partial-ordering based ILP model for the graph coloring problem (GCP) and the bandwidth coloring problem (BCP). The GCP asks for…
Strengthened Partial-Ordering Based ILP Models for the Vertex Coloring Problem
Adalat Jabrayilov, Petra Mutzel
The vertex coloring problem asks for the minimum number of colors that can be assigned to the vertices of a given graph such that each two adjacent vertices get different colors. F…
On the hop-constrained Steiner tree problems
Adalat Jabrayilov
The hop-constrained Steiner tree problem (HSTP) is a generalization of the classical Steiner tree problem. It asks for a minimum cost subtree that spans some specified nodes of a g…
A new Integer Linear Program for the Steiner Tree Problem with Revenues, Budget and Hop Constraints
Adalat Jabrayilov, Petra Mutzel
The Steiner tree problem with revenues, budgets and hop constraints (STPRBH) is a variant of the classical Steiner tree problem. This problem asks for a subtree in a given graph wi…
New Integer Linear Programming Models for the Vertex Coloring Problem
Adalat Jabrayilov, Petra Mutzel
The vertex coloring problem asks for the minimum number of colors that can be assigned to the vertices of a given graph such that for all vertices v the color of v is different fro…
Compact Layered Drawings of General Directed Graphs
Adalat Jabrayilov, Sven Mallach, Petra Mutzel +2
We consider the problem of layering general directed graphs under height and possibly also width constraints. Given a directed graph G = (V,A) and a maximal height, we propose a la…