English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The famous Chinese Postman Problem (CPP) is polynomial time solvable on bothundirected and directed graphs. Gutin et al. [Discrete Applied Math 217 (2016)]generalized these results by proving that CPP on $c$-edge-colored graphs ispolynomial time solvable for every $c\geq 2$. In CPP on weighted edge-coloredgraphs $G$, we wish to find a minimum weight properly colored closed walkcontaining all edges of $G$ (a walk is properly colored if every twoconsecutive edges are of different color, including the last and first edges ina closed walk). In this paper, we consider CPP on arc-colored digraphs (forproperly colored closed directed walks), and provide a polynomial-timealgorithm for the problem on weighted 2-arc-colored digraphs. This is asomewhat surprising result since it is NP-complete to decide whether a2-arc-colored digraph has a properly colored directed cycle [Gutin et al.,Discrete Math 191 (1998)]. To obtain the polynomial-time algorithm, wecharacterize 2-arc-colored digraphs containing properly colored Euler trails.

The Euler and Chinese Postman Problems on 2-Arc-Colored Digraphs