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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the partial search order problem (PSOP) proposed recently byScheffler [WG 2022]. Given a graph $G$ together with a partial order over theset of vertices of $G$, this problem determines if there is an$\mathcal{S}$-ordering that is consistent with the given partial order, where$\mathcal{S}$ is a graph search paradigm like BFS, DFS, etc. This problemnaturally generalizes the end-vertex problem which has received much attentionover the past few years. It also generalizes the so-called ${\mathcal{F}}$-treerecognition problem which has just been studied in the literature recently. Ourmain contribution is a polynomial-time dynamic programming algorithm for thePSOP of the maximum cardinality search (MCS) restricted to chordal graphs. Thisresolves one of the most intriguing open questions left in the work ofScheffler [WG 2022]. To obtain our result, we propose the notion of layerstructure and study numerous related structural properties which might be ofindependent interest.

A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs