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

A set $S$ of isometric paths of a graph $G$ is "$v$-rooted", where $v$ is avertex of $G$, if $v$ is one of the end-vertices of all the isometric paths in$S$. The isometric path complexity of a graph $G$, denoted by $ipco(G)$, is theminimum integer $k$ such that there exists a vertex $v\in V(G)$ satisfying thefollowing property: the vertices of any isometric path $P$ of $G$ can becovered by $k$ many $v$-rooted isometric paths.  First, we provide an $O(n^2 m)$-time algorithm to compute the isometric pathcomplexity of a graph with $n$ vertices and $m$ edges. Then we show that theisometric path complexity remains bounded for graphs in three seeminglyunrelated graph classes, namely, hyperbolic graphs, (theta, prism,pyramid)-free graphs, and outerstring graphs. Hyperbolic graphs are extensivelystudied in Metric Graph Theory. The class of (theta, prism, pyramid)-freegraphs are extensively studied in Structural Graph Theory, e.g. in the contextof the Strong Perfect Graph Theorem. The class of outerstring graphs is studiedin Geometric Graph Theory and Computational Geometry. Our results also showthat the distance functions of these (structurally) different graph classes aremore similar than previously thought.  There is a direct algorithmic consequence of having small isometric pathcomplexity. Specifically, we show that if the isometric path complexity of agraph $G$ is bounded by a constant, then there exists a polynomial-timeconstant-factor approximation algorithm for ISOMETRIC PATH COVER, whoseobjective is to cover all vertices of a graph with a minimum number ofisometric paths. This applies to all the above graph classes.

Isometric path complexity of graphs