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

A mixed multigraph is a multigraph which may contain both undirected anddirected edges. An orientation of a mixed multigraph $G$ is an assignment ofexactly one direction to each undirected edge of $G$. A mixed multigraph $G$can be oriented to a strongly connected digraph if and only if $G$ isbridgeless and strongly connected [Boesch and Tindell, Am. Math. Mon., 1980].For each $r \in \mathbb{N}$, let $f(r)$ denote the smallest number such thatany strongly connected bridgeless mixed multigraph with radius $r$ can beoriented to a digraph of radius at most $f(r)$. We improve the current bestupper bound of $4r^2+4r$ on $f(r)$ [Chung, Garey and Tarjan, Networks, 1985] to$1.5 r^2 + r + 1$. Our upper bound is tight upto a multiplicative factor of$1.5$ since, $\forall r \in \mathbb{N}$, there exists an undirected bridgelessgraph of radius $r$ such that every orientation of it has radius at least $r^2+ r$ [Chv\'atal and Thomassen, J. Comb. Theory. Ser. B., 1978]. We prove amarginally better lower bound, $f(r) \geq r^2 + 3r + 1$, for mixed multigraphs.While this marginal improvement does not help with asymptotic estimates, itclears a natural suspicion that, like undirected graphs, $f(r)$ may be equal to$r^2 + r$ even for mixed multigraphs. En route, we show that if each edge of$G$ lies in a cycle of length at most $\eta$, then the oriented radius of $G$is at most $1.5 r \eta$. All our proofs are constructive and lend themselves topolynomial time algorithms.

Improved Bounds for the Oriented Radius of Mixed Multigraphs