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

In the present paper, we study algorithmic questions for the arc-intersectiongraph of directed paths on a tree. Such graphs are known to be perfect (provedby Monma and Wei in 1986). We present faster algorithms than all previouslyknown algorithms for solving the minimum coloring and the minimum clique coverproblems. They both run in $O(np)$ time, where $n$ is the number of vertices ofthe tree and $p$ the number of paths. Another result is a polynomial algorithmcomputing a kernel in the intersection graph, when its edges are oriented in aclique-acyclic way. Indeed, such a kernel exists for any perfect graph by atheorem of Boros and Gurvich. Such algorithms computing kernels are known onlyfor few classes of perfect graphs.

Directed paths on a tree: coloring, multicut and kernel