Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Finding All Useless Arcs in Directed Planar Graphs   We present a linear-time algorithm for simplifying flow networks on directed
planar graphs: Given a directed planar graph on $n$ vertices, a source vertex
$s$ and a sink vertex $t$, our algorithm removes all the arcs that do not
participate in any simple $s,t$-path in linear-time. The output graph produced
by our algorithm satisfies the prerequisite needed by the $O(n\log n)$-time
algorithm of Weihe [FOCS'94 \& JCSS'97] for computing maximum $s,t$-flow in
directed planar graphs. Previously, Weihe's algorithm could not run in $O(n\log
n)$-time due to the absence of the preprocessing step; all the preceding
algorithms run in $\tilde{\Omega}(n^2)$-time [Misiolek-Chen, COCOON'05 \&
IPL'06; Biedl, Brejov{\'{a}} and Vinar, MFCS'00]. Consequently, this provides
an alternative $O(n\log n)$-time algorithm for computing maximum $s,t$-flow in
directed planar graphs in addition to the known $O(n\log n)$-time algorithms
[Borradaile-Klein, SODA'06 \& J.ACM'09; Erickson, SODA'10].
  Our algorithm can be seen as a (truly) linear-time $s,t$-flow sparsifier for
directed planar graphs, which runs faster than any maximum $s,t$-flow algorithm
(which can also be seen of as a sparsifier). The simplified structures of the
resulting graph might be useful in future developments of maximum $s,t$-flow
algorithms in both directed and undirected planar graphs.

2
The categories of this paper are: math
16
The categories of this paper are: stat
22
The categories of this paper are: chao-dyn
30
The categories of this paper are: q-alg
20
The categories of this paper are: acc-phys
13
The categories of this paper are: quant-ph
4
The categories of this paper are: cond-mat
17
The categories of this paper are: q-fin
36
The categories of this paper are: cmp-lg
15
The categories of this paper are: nucl-ex
26
The categories of this paper are: bayes-an
21
The categories of this paper are: adap-org
29
The categories of this paper are: funct-an
11
The categories of this paper are: hep-lat
31
The categories of this paper are: ao-sci
7
The categories of this paper are: hep-th