Edge-arc-disjoint paths in semicomplete mixed graphs

J. Bang-Jensen*, Y. Wang

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstract

The so-called weak-2-linkage problem asks for a given digraph (Formula presented.) and distinct vertices (Formula presented.) of (Formula presented.) whether (Formula presented.) has arc-disjoint paths (Formula presented.) so that (Formula presented.) is an (Formula presented.) -path for (Formula presented.). This problem is NP-complete for general digraphs but the first author showed that the problem is polynomially solvable and that all exceptions can be characterized when (Formula presented.) is a semicomplete digraph, that is, a digraph with no pair of nonadjacent vertices. In this paper we extend these results to paths which are both edge-disjoint and arc-disjoint in semicomplete mixed graphs, that is, a mixed graph (Formula presented.) in which every pair of distinct vertices has either an arc, an edge, or both an arc and an edge between them. We give a complete characterization of the negative instances and explain how this gives rise to a polynomial algorithm for the problem.

OriginalsprogEngelsk
TidsskriftJournal of Graph Theory
ISSN0364-9024
DOI
StatusE-pub ahead of print - 4. nov. 2024

Fingeraftryk

Dyk ned i forskningsemnerne om 'Edge-arc-disjoint paths in semicomplete mixed graphs'. Sammen danner de et unikt fingeraftryk.

Citationsformater