|
[1] G. Borradaile, D. Eppstein, A. Nayyeri, and C. Wulff-Nilsen. All-pairs minimum
cuts in near-linear time for surface-embedded graphs. Computing Research Repository,
2014. http://arxiv.org/abs/1411.7055.
[2] G. Borradaile and P. N. Klein. An O(n log n) algorithm for maximum st-flow in a
directed planar graph. Journal of the ACM, 56(2):9.1–9.30, 2009.
[3] G. Borradaile, P. N. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen. Multiplesource
multiple-sink maximum flow in directed planar graphs in near-linear time.
In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer
Science, pages 170–179, 2011.
[4] G. Borradaile, P. Sankowski, and C. Wulff-Nilsen. Min st-cut oracle for planar
graphs with near-linear preprocessing time. ACM Transactions on Algorithms,
11(3):16.1–16.29, 2015.
[5] U. Brandes and D. Wagner. A linear time algorithm for the arc disjoint menger
problem in planar directed graphs. Algorithmica, 28(1):16–36, 2000.
[6] S. Cabello. Finding shortest contractible and shortest separating cycles in embedded
graphs. ACM Transactions on Algorithms, 6(2):24.1–24.18, 2010.
[7] S. Cabello, E. W. Chambers, and J. Erickson. Multiple-source shortest paths in
embedded graphs. SIAM Journal Computing, 42(4):1542–1571, 2013.
[8] S. Cabello, É. Colin de Verdière, and F. Lazarus. Finding shortest non-trivial cycles
31
in directed graphs on surfaces. In Proceedings of the 26th ACM Symposium on
Computational Geometry, pages 156–165, 2010.
[9] P. Chalermsook, J. Fakcharoenphol, and D. Nanongkai. A deterministic near-linear
time algorithm for finding minimum cuts in planar graphs. In Proceedings of the
15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 828–829, 2004.
[10] H.-C. Chang and H.-I. Lu. Computing the girth of a planar graph in linear time.
SIAM Journal on Computing, 42(3):1077–1094, 2013.
[11] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms.
MIT Press, 3rd edition, 2009.
[12] M. Cygan, H. N. Gabow, and P. Sankowski. Algorithmic applications of BaurStrassen’s
theorem: Shortest cycles, diameter and matchings. In Proceedings of the
53rd Annual IEEE Symposium on Foundations of Computer Science, pages 531–540,
2012.
[13] H. Djidjev. A faster algorithm for computing the girth of planar and bounded genus
graphs. ACM Transactions on Algorithms, 7(1):3.1–3.16, 2010.
[14] D. Eisenstat and P. N. Klein. Linear-time algorithms for max flow and multiplesource
shortest paths in unit-weight planar graphs. In Proceedings of the 45th ACM
Symposium on Theory of Computing, pages 735–744, 2013.
[15] J. Erickson. Maximum flows and parametric shortest paths in planar graphs. In Proceedings
of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pages
794–804, 2010.
[16] J. Erickson, K. Fox, and A. Nayyeri. Global minimum cuts in surface embedded
graphs. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 1309–1318, 2012.
[17] J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete &
Computational Geometry, 31(1):37–59, 2004.
32
[18] J. Erickson and A. Nayyeri. Shortest non-crossing walks in the plane. In Proceedings
of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 297–208,
2011.
[19] J. Erickson and P. Worah. Computing the shortest essential cycle. Discrete & Computational
Geometry, 44(4):912–930, 2010.
[20] J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths,
and near linear time. Journal of Computer and System Sciences, 72(5):868–889,
2006.
[21] K. Fox. Shortest non-trivial cycles in directed and undirected surface graphs. In Proceedings
of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages
352–364, 2013.
[22] K. Fox. Fast algorithms for surface embedded graphs via homology. PhD thesis,
University of Illinois at Urbana-Champaign, 2014.
[23] G. N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications.
SIAM Journal on Computing, 16(6):1004–1022, 1987.
[24] H. N. Gabow. A matroid approach to finding edge connectivity and packing arborescences.
Journal of Computer and System Sciences, 50(2):259–273, 1995.
[25] H. N. Gabow and R. E. Tarjan. Faster scaling algorithms for network problems.
SIAM Journal on Computing, 18(5):1013–1036, 1989.
[26] P. Gawrychowski, S. Mozes, and O. Weimann. Submatrix maximum queries in
Monge matrices are equivalent to predecessor search. In B. Speckmann, editor,
Proceedings of the 42nd International Colloquium on Automata, Languages, and
Programming, 2015, to appear.
[27] A. V. Goldberg. Scaling algorithms for the shortest paths problem. SIAM Journal
on Computing, 24(3):494–504, 1995.
33
[28] R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the SIAM,
9(4):551–570, 1961.
[29] M. T. Goodrich. Planar separators and parallel polygon triangulation. Journal of
Computer and System Sciences, 51(3):374–389, 1995.
[30] J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed
graph. Journal of Algorithms, 17(3):424–446, 1994.
[31] M. R. Henzinger, P. N. Klein, S. Rao, and S. Subramanian. Faster shortest-path
algorithms for planar graphs. Journal of Computer and System Sciences, 55(1):3–23,
1997.
[32] A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM Journal on
Computing, 7(4):413–423, 1978.
[33] G. F. Italiano, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. Improved algorithms
for min cut and max flow in undirected planar graphs. In Proceedings of the
43rd ACM Symposium on Theory of Computing, pages 313–322, 2011.
[34] L. Janiga and V. Koubek. Minimum cut in directed planar networks. Kybernetika,
28(1):37–49, 1992.
[35] H. Kaplan, S. Mozes, Y. Nussbaum, and M. Sharir. Submatrix maximum queries in
Monge matrices and Monge partial matrices, and their applications. In Proceedings
of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 338–355,
2012.
[36] H. Kaplan and Y. Nussbaum. Minimum s-t cut in undirected planar graphs when the
source and the sink are close. In T. Schwentick and C. Dürr, editors, Proceedings
of the 28th International Symposium on Theoretical Aspects of Computer Science,
pages 117–128, 2011.
[37] D. R. Karger. Minimum cuts in near-linear time. Journal of the ACM, 47(1):46–76,
2000.
34
[38] K.-i. Kawarabayashi and M. Thorup. Deterministic global minimum cut of a simple
graph in near-linear time. In Proceedings of the 47th ACM Symposium on Theory of
Computing, pages 665–674, 2015.
[39] S. Khuller and J. Naor. Flow in planar graphs: A survey of recent results. In Planar
Graphs, DIMACS Series in Discrete Math and Theoretical Computer Science 9,
pages 59–84. AMS, 1993.
[40] P. N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the
16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 146–155, 2005.
[41] P. N. Klein, S. Mozes, and C. Sommer. Structured recursive separator decompositions
for planar graphs in linear time. In Proceedings of the 45th ACM Symposium
on Theory of Computing, pages 505–514, 2013.
[42] P. N. Klein, S. Mozes, and O. Weimann. Shortest paths in directed planar graphs with
negative lengths: A linear-space O(n log2 n)-time algorithm. ACM Transactions on
Algorithms, 6(2):30.1–30.18, 2010.
[43] J. Lacki, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. Single source - all sinks
max flows in planar digraphs. In Proceedings of the 53rd Annual IEEE Symposium
on Foundations of Computer Science, pages 599–608, 2012.
[44] J. Lacki and P. Sankowski. Min-cuts and shortest cycles in planar graphs in
O(n log log n) time. In Proceedings of the 19th Annual European Symposium on
Algorithms, pages 155–166, 2011.
[45] A. Lingas and E.-M. Lundell. Efficient approximation algorithms for shortest cycles
in undirected graphs. Information Processing Letters, 109(10):493–498, 2009.
[46] R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal
on Applied Mathematics, 36:177–189, 1979.
[47] B. Monien. The complexity of determining a shortest cycle of even length. Computing,
31(4):355–369, 1983.
35
[48] S. Mozes, Y. Nussbaum, and O. Weimann. Faster shortest paths in dense distance
graphs, with applications. Computing Research Repository, 2014. http://arxiv.
org/abs/1404.0977.
[49] S. Mozes and C. Wulff-Nilsen. Shortest paths in planar graphs with real lengths in
O(n log2 n/ log log n) time. In M. de Berg and U. Meyer, editors, Proceedings of
the 18th Annual European Symposium on Algorithms, Lecture Notes in Computer
Science 6347, pages 206–217. Springer, 2010.
[50] H. Nagamochi and T. Ibaraki. Computing edge-connectivity in multigraphs and
capacitated graphs. SIAM Journal on Discrete Mathematics, 5(1):54–66, 1992.
[51] J. B. Orlin. Max flows in O(nm) time, or better. In Proceedings of the 45th ACM
Symposium on Theory of Computing, pages 765–774, 2013.
[52] E. Papadopoulou. k-pairs non-crossing shortest paths in a simple polygon. International
Journal of Computational Geometry and Applications, 9(6):533–552, 1999.
[53] V. Polishchuk and J. S. B. Mitchell. Thick non-crossing paths and minimum-cost
flows in polygonal domains. In Proceedings of the 23rd ACM Symposium on Computational
Geometry, pages 56–65, 2007.
[54] J. H. Reif. Minimum s-t cut of a planar undirected network in O(n log2 n) time.
SIAM Journal on Computing, 12(1):71–81, 1983.
[55] L. Roditty and R. Tov. Approximating the girth. ACM Transactions on Algorithms,
9(2):15.1–15.13, 2013.
[56] L. Roditty and V. Vassilevska Williams. Subquadratic time approximation algorithms
for the girth. In Proceedings of the 23rd Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 833–845, 2012.
[57] M. Stoer and F. Wagner. A simple min-cut algorithm. Journal of the ACM,
44(4):585–591, 1997.
36
[58] J. Takahashi, H. Suzuki, and T. Nishizeki. Finding shortest non-crossing rectilinear
paths in plane regions. In Proceedings of the 4th International Symposium on
Algorithms and Computation, pages 98–107, 1993.
[59] J.-y. Takahashi, H. Suzuki, and T. Nishizeki. Shortest noncrossing paths in plane
graphs. Algorithmica, 16(3):339–357, 1996.
[60] V. Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd.
In Proceedings of the 44th ACM Symposium on Theory of Computing, pages
887–898, 2012.
[61] V. Vassilevska Williams and R. Williams. Subcubic equivalences between path,
matrix and triangle problems. In Proceedings of the 51st Annual IEEE Symposium
on Foundations of Computer Science, pages 645–654, 2010.
[62] K. Weihe. Edge-disjoint (s, t)-paths in undirected planar graphs in linear time. Journal
of Algorithms, 23(1):121–138, 1997.
[63] O. Weimann and R. Yuster. Computing the girth of a planar graph in O(n log n)
time. SIAM Journal on Discrete Mathematics, 24(2):609–616, 2010.
[64] C. Wulff-Nilsen. Algorithms for planar graphs and graphs in metric spaces. PhD
thesis, University of Copenhagen, 2010.
[65] R. Yuster. A shortest cycle for each vertex of a graph. Information Processing
Letters, 111(21-22):1057–1061, 2011.
[66] R. Yuster and U. Zwick. Finding even cycles even faster. SIAM Journal on Discrete
Mathematics, 10(2):209–222, 1997.
|