Explanipedia

A Customized SAT-based Solver for Graph Coloring Open

Teun van den Brand, Daniel Faber, Stephan Held · 2025

We introduce ZykovColor, a novel SAT-based algorithm to solve the graph coloring problem working on top of an encoding that mimics the Zykov tree. Our method is based on an approach of Hébrard and Katsirelos (2020) that employs a propagato…

Cost-Distance Steiner Trees for Timing-Constrained Global Routing Open

Stephan Held, Edgar Perner · 2025

The cost-distance Steiner tree problem seeks a Steiner tree that minimizes the total congestion cost plus the weighted sum of source-sink delays. This problem arises as a subroutine in timing-constrained global routing with a linear delay …

Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks Open

Jannis Blauth, Stephan Held, Dirk Müller, Niklas Schlomberg, Vera Traub , et al. · 2024

We develop theoretical foundations and practical algorithms for vehicle routing with time-dependent travel times. We also provide new benchmark instances and experimental results. First, we study basic operations on piecewise linear arriva…

Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem Open

Josefine Foos, Stephan Held, Yannik Kyle Dustin Spitzley · 2023

Uniform cost-distance Steiner trees minimize the sum of the total length and weighted path lengths from a dedicated root to the other terminals. They are applied when the tree is intended for signal transmission, e.g. in chip design or tel…

Further Improvements on Approximating the Uniform Cost-Distance Steiner Tree Problem Open

Stephan Held, Yannik Kyle Dustin Spitzley · 2022

In this paper, we consider the Uniform Cost-Distance Steiner Tree Problem in metric spaces, a generalization of the well-known Steiner tree problem. Cost-distance Steiner trees minimize the sum of the total length and the weighted path len…

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks Open

Jannis Blauth, Stephan Held, Dirk Müller, Niklas Schlomberg, Vera Traub , et al. · 2022

We develop theoretical foundations and practical algorithms for vehicle routing with time-dependent travel times. We also provide new benchmark instances and experimental results. First, we study basic operations on piecewise linear arriva…

Approximating the discrete time-cost tradeoff problem with bounded depth Open

Siad Daboul, Stephan Held, Jens Vygen · 2022

We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is den…

Constrained Local Search for Last-Mile Routing Open

William R. Cook, Stephan Held, Keld Helsgaun · 2021

Last-mile routing refers to the final step in a supply chain, delivering packages from a depot station to the homes of customers. At the level of a single van driver, the task is a traveling salesman problem. But the choice of route may be…

Approximating the discrete time-cost tradeoff problem with bounded depth Open

Siad Daboul, Stephan Held, Jens Vygen · 2020

We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is den…

Vehicle routing with subtours Open

Stephan Held, Jochen Könemann, Jens Vygen · 2019

Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two Open

Stephan Held, Sophie Spirkl · 2017

We consider the problem of constructing fast and small binary adder circuits. Among widely used adders, the Kogge-Stone adder is often considered the fastest, because it computes the carry bits for two n -bit numbers (where n is a power of…

Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and\n Fan-Out Two Open

Stephan Held, Sophie Spirkl · 2015

We consider the problem of constructing fast and small binary adder circuits.\nAmong widely-used adders, the Kogge-Stone adder is often considered the\nfastest, because it computes the carry bits for two $n$-bit numbers (where $n$\nis a po…

Two-Level Rectilinear Steiner Trees Open

Stephan Held, Nicolas Kämmerling · 2015

Given a set $P$ of terminals in the plane and a partition of $P$ into $k$ subsets $P_1, ..., P_k$, a two-level rectilinear Steiner tree consists of a rectilinear Steiner tree $T_i$ connecting the terminals in each set $P_i$ ($i=1,...,k$) a…

Stephan Held YOU? Author Swipe