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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We propose faster algorithms for the maximum flow problem and shortest path problems based on graph decomposition. Our algorithms first construct indices (data structures) from a given graph, then use them for solving the problems. Time complexities of our algorithms depend on the size of the maximum triconnected component in the graph, say r. Max flow indexing problem is a basic network flow problem, which consists of two phases. In a preprocessing phase we construct an index and in a query phase we process the query using the index. We can solve all pairs maximum flow problem and minimum cut problem using the indices. Our algorithms run faster than known algorithms if r is small. The maximum flow problem can be solved in O(nr) time, which is faster than the best known O(nm) algorithm [29] if r = o(m), where n and m are the numbers of vertices and edges in the given network, respectively. Distance oracle problem is a basic problem in shortest path, consisting of two phases. In preprocessing phase we construct index and in query phase we use the index to find shortest path between two vertices. We use these indices to solve single source shortest path and all pair shortest path problems. If the given graph is undirected and all the weights are non-negative integers, then our algorithm finds shortest path between two vertices in O(m) time. If the given graph is directed or the weights are non-negative real numbers then our algorithm finds shortest path between two vertices in O(m + n log r) time. If the edge weights are real numbers (i.e some of the weights are negative) then our algorithm finds shortest path between two vertices in O(m + nr) time. Submitted: March 2018 Reviewed: February 2019 Revised: March 2019 Accepted: April 2019 Final: Septemebr 2019 Published: October 2019 Article type: Regular Paper Communicated by: M.S. Rahman, W.-K. Sung, R. Uehara Preliminary version of this work appeared in 12th International Conference and Workshops on Algorithms and Computation (WALCOM), pages 80-92, 2018. The work is supported by JSPS KAKENHI 16K12393 and JST CREST JPMJCR1402. E-mail addresses: manasjk@cse.iitm.ac.in (Manas Jyoti Kashyop) tsunehiko nagayama@me2.mist.i.utokyo.ac.jp (Tsunehiko Nagayama) sada@mist.i.u-tokyo.ac.jp (Kunihiko Sadakane) 782 Kashyop et al. Faster algorithms for shortest path and network flow

Faster algorithms for shortest path and network flow based on graph decomposition