5 papers
Implicit Hitting Set Enumeration for Power Dominating Sets
Thomas Bläsius, Max Göttlicher, Martin Schirneck
The Transversal Hypergraph problem asks to enumerate (list) all inclusion-minimal hitting sets of a hypergraph. It usually assumes that the input is completely known and does not c…
From FPT to W[P]: Classifying Zero Forcing, Power Domination and Their Variants
Max Göttlicher, Lennard Hofmann, Christoph Niederbudde
Zero Forcing (ZF) and Power Dominating Set (PDS) mark vertices in a graph based on a common forcing process starting from a problem-specific set of initially marked vertices. ZF in…
Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem
Thomas Bläsius, Henrik Csöre, Max Göttlicher +2
Motivated by hierarchical networks, we introduce the Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree (FLaMECaST) problem, a variant of the Euclidean Steiner tree wi…
The Constrained Layer Tree Problem and Applications to Solar Farm Cabling
Thomas Bläsius, Max Göttlicher, Sascha Gritzbach +1
Motivated by the cabling of solar farms, we study the problem Constrained Layer Tree. At its core, it asks whether there exists a tree that connects a set of sources (the leaves) t…
An Efficient Algorithm for Power Dominating Set
Thomas Bläsius, Max Göttlicher
The problem Power Dominating Set (PDS) is motivated by the placement of phasor measurement units to monitor electrical networks. It asks for a minimum set of vertices in a graph th…