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/

Zendy Plus

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

Zendy Tools

Zendy Open

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k−1)-dimensional spaceR k−1,f∶V→R k−1, such that no hyperplane containsk points of {f(v)|v∈V}, and for eachv∈V−X, f(v) is in the convex hull of {f(w)| (v, w)∈E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in “Rubber bands, convex embeddings and graph connectivity”,Combinatorica 8 (1988), 91–102. Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n 2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n 0.19; e.g., for\(k = \sqrt n \), the factor of improvement is >n 0.62. Both algorithms have processor efficient parallel versions that run inO((logn)2) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn 2/(logn)3 while having the same running time. Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph.

Directeds-t numberings, Rubber bands, and testing digraphk-vertex connectivity