Computing directed Steiner path covers

Frank Gurski (), Dominique Komander (), Carolin Rehs (), Jochen Rethmann () and Egon Wanke ()
Additional contact information
Frank Gurski: Heinrich Heine University Düsseldorf
Dominique Komander: Heinrich Heine University Düsseldorf
Carolin Rehs: Heinrich Heine University Düsseldorf
Jochen Rethmann: Niederrhein University of Applied Sciences
Egon Wanke: Heinrich Heine University Düsseldorf

Journal of Combinatorial Optimization, 2022, vol. 43, issue 2, No 6, 402-431

Abstract: Abstract In this article we consider the Directed Steiner Path Cover problem on directed co-graphs. Given a directed graph $$G=(V,E)$$ G = ( V , E ) and a set $$T \subseteq V$$ T ⊆ V of so-called terminal vertices, the problem is to find a minimum number of vertex-disjoint simple directed paths, which contain all terminal vertices and a minimum number of non-terminal vertices (Steiner vertices). The primary minimization criteria is the number of paths. We show how to compute in linear time a minimum Steiner path cover for directed co-graphs. This leads to a linear time computation of an optimal directed Steiner path on directed co-graphs, if it exists. Since the Steiner path problem generalizes the Hamiltonian path problem, our results imply the first linear time algorithm for the directed Hamiltonian path problem on directed co-graphs. We also give binary integer programs for the (directed) Hamiltonian path problem, for the (directed) Steiner path problem, and for the (directed) Steiner path cover problem. These integer programs can be used to minimize change-over times in pick-and-place machines used by companies in electronic industry.

Keywords: Binary integer program; Combinatorial optimization; Directed co-graphs; Directed Steiner path cover problem; Directed Steiner path problem; Directed Hamiltonian path problem; Pick-and-place machines (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00781-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:43:y:2022:i:2:d:10.1007_s10878-021-00781-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00781-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().