-
Notifications
You must be signed in to change notification settings - Fork 2
/
optimization.bib
3928 lines (3591 loc) · 138 KB
/
optimization.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%% This BibTeX bibliography file was created using BibDesk.
%% https://bibdesk.sourceforge.io/
%% Created for Jeff Erickson at 2024-11-10 21:03:54 -0600
%% Saved with string encoding Unicode (UTF-8)
@article{gt-anda-87,
author = {Gilbert, John R. and Tarjan, Robert E.},
date-added = {2024-11-10 20:29:23 -0600},
date-modified = {2024-11-10 21:03:54 -0600},
doi = {10.1007/BF01396660},
journal = {Numerische Mathematik},
number = {4},
pages = {377--404},
title = {The analysis of a nested dissection algorithm},
volume = {50},
year = {1987}}
@article{mv-ndsnb-93,
author = {julio M. Stern and Vavasis, Stephen A.},
date-added = {2024-09-22 17:19:10 -0500},
date-modified = {2024-09-22 17:22:15 -0500},
doi = {10.1137/0614054},
journal = {SIAM J. Matrix Analysis Appl.},
number = {1},
pages = {766--775},
title = {Nested dissection for sparse nullspace bases},
volume = {14},
year = {1993},
bdsk-url-1 = {https://doi.org/10.1137/0614054}}
@article{ay-msnda-13,
author = {Alon, Noga and Yuster, Raphael},
date-added = {2024-09-22 16:28:28 -0500},
date-modified = {2024-09-22 16:36:34 -0500},
doi = {https://doi.org/10.1145/2508028.2505989},
journal = {J. ACM},
number = {4},
pages = {article 25, 18pp.},
title = {Matrix sparsification and nested dissection over arbitrary fields},
volume = {60},
year = {2013},
bdsk-url-1 = {https://doi.org/10.1145/2508028.2505989}}
@inproceedings{y-msrdc-08,
author = {Yuster, Raphael},
booktitle = {Proc. 49th IEEE Symp. Found. Comput. Sci.},
date-added = {2024-09-22 16:24:24 -0500},
date-modified = {2024-09-22 16:36:49 -0500},
doi = {10.1109/FOCS.2008.14},
pages = {137--145},
title = {Matrix sparsification for rank and determinant computations via nested dissection},
year = {2008},
bdsk-url-1 = {https://doi.org/10.1109/FOCS.2008.14}}
@article{p-esr-79,
author = {Papadimitriou, Christos H.},
date-added = {2024-08-03 17:53:29 -0500},
date-modified = {2024-08-03 17:53:49 -0500},
doi = {10.1016/0020-0190(79)90079-6},
journal = {Information Processing Letters},
keywords = {Binary search, Farey series, linear programming},
number = {1},
pages = {1--4},
title = {Efficient search for rationals},
volume = {8},
year = {1979},
bdsk-url-1 = {https://doi.org/10.1016/0020-0190(79)90079-6}}
@inproceedings{ca-prrid-76,
author = {Collins, George E. and Akritas, Alkiviadis G.},
booktitle = {Proc. 3rd {ACM} Symp. Symbolic and Algebraic Manipulation},
comments = {Yes, the title is misspelled.},
date-added = {2024-08-03 17:33:31 -0500},
date-modified = {2024-08-03 17:35:15 -0500},
doi = {10.1145/800205.806346},
pages = {272--275},
title = {Polynomial real root isolation using {Descarte's} (sic) rule of signs},
year = {1976},
bdsk-url-1 = {https://doi.org/10.1145/800205.806346}}
@book{gv-mc-13,
author = {Golub, Gene H. and Van Loan, Charles F.},
date-added = {2024-07-16 15:42:19 -0500},
date-modified = {2024-07-16 15:46:09 -0500},
doi = {10.1137/1.9781421407944},
edition = {Fourth},
publisher = {Johns Hopkins University Press},
title = {Matrix Computations},
year = {2013},
bdsk-url-1 = {https://doi.org/10.1137/1.9781421407944}}
@article{jo-rnfns-09,
abstract = {This paper was edited by Sigismund Cohn, C. W. Borchardt and A. Clebsch from posthumous manuscripts of C. G. J. Jacobi. The solution of the following problem: ``to transform a square table of m2 numbers by adding minimal numbers ℓito each horizontal row, in such a way that it possess m transversal maxima'', determines the order and the shortest normal form reduction of the system: the equations ui= 0 must be respectively differentiated ℓitimes. One also determines the number of differentiations of each equation of the given system needed to produce the differential equations necessary to reduce the proposed system to a single equation.},
author = {Jacobi, Carl Gustav Jacob and Ollivier (translator), Fran{\c c}ois},
date-added = {2023-03-11 15:07:06 -0600},
date-modified = {2023-03-11 15:12:47 -0600},
doi = {10.1007/s00200-009-0088-2},
journal = {Appl. Algebra Eng. Commun. Comput.},
note = {Engish translation of \cite{j-adsnf-1890}},
number = {1},
pages = {33--64},
title = {The reduction to normal form of a non-normal system of differential equations},
volume = {20},
year = {2009},
bdsk-url-1 = {https://doi.org/10.1007/s00200-009-0088-2}}
@article{10.1093/imamat/7.3.273,
abstract = {{Problems involving the determination of routes on networks arise in many different contexts. For example network flow problems in operations research, such as transportation and assignment problems, involve the determination of a succession of shortest or least-cost paths between commodity sources and sinks. Again, critical path analysis and certain scheduling problems involve the determination of longest paths on activity networks. Pathfinding problems of different kinds also arise in the design of logic networks, and in routing messages through congested communication networks. This paper presents an algebraic structure for the formulation and solution of such problems.After defining the algebraic structure and giving concrete examples applicable to different kinds of routing problems, we use it in a general analysis of a class of directed networks, in which each are has an associated measure (representing for instance a transportation cost, an activity duration, the state (open or closed) of a switch, or the probability of a communication link being available). It is then shown that all the routing problems mentioned above can be expressed in the same algebraic form, and that they can all be solved by variants of classical methods of linear algebra, differing from these only in the significance of the additive and multiplicative operations.}},
author = {Carr{\'e}, Bernard A.},
date-added = {2023-03-11 13:38:21 -0600},
date-modified = {2023-03-11 13:39:22 -0600},
doi = {10.1093/imamat/7.3.273},
journal = {IMA J. Appl. Math.},
keywords = {min-plus algebra, shortest paths and flows via funny matrix stuff},
number = {3},
pages = {273--294},
title = {An Algebra for Network Routing Problems},
volume = {7},
year = {1971},
bdsk-url-1 = {https://doi.org/10.1093/imamat/7.3.273}}
@article{flspw-fppcg-18,
arxiv = {1511.01379},
author = {Fomin, Fedor V. and Lokshtanov, Daniel and Saurabh, Saket and Pilipczuk, Micha{\l} and Wrochna, Marcin},
date-added = {2021-06-28 16:20:45 -0500},
date-modified = {2021-06-28 16:20:45 -0500},
doi = {10.1145/3186898},
journal = {ACM Trans. Algorithms},
number = {3},
pages = {34:1--34:45},
title = {Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth},
volume = {14},
year = {2018},
bdsk-url-1 = {https://doi.org/10.1145/3186898}}
@inproceedings{aww-afpsa-16,
author = {Abboud, Amir and Williams, Virginia Vassilevska and Wang, Joshua R.},
booktitle = {Proc. 27th Ann. ACM-SIAM Symp. Discrete Algorithms},
date-added = {2021-06-28 16:20:21 -0500},
date-modified = {2021-06-28 16:20:21 -0500},
doi = {10.1137/1.9781611974331.ch28},
pages = {377--391},
read = {1},
title = {Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs},
year = {2016},
bdsk-url-1 = {https://doi.org/10.1137/1.9781611974331.ch28}}
@article{sw-sma-97,
author = {Stoer, Mechthild and Wagner, Frank},
date-added = {2021-06-28 16:20:03 -0500},
date-modified = {2021-06-28 16:20:03 -0500},
doi = {10.1145/263867.263872},
journal = {J. ACM},
number = {4},
pages = {585--591},
title = {A simple min-cut algorithm},
volume = {44},
year = {1997},
bdsk-url-1 = {https://doi.org/10.1145/263867.263872}}
@techreport{f-eani-94,
address = {Budapest},
author = {Frank, Andr{\'a}s},
date-added = {2021-06-28 16:19:17 -0500},
date-modified = {2021-06-28 16:19:17 -0500},
institution = {Egerv{\'a}ry Research Group, E{\"o}tv{\"o}s University,},
note = {Written at Laboratoire Artemis, IMAG, Universit{\'e} J. Fourier, Grenoble, March 1994.},
number = {QP-2009-01},
title = {On the edge-connectivity algorithm of {Nagamochi} and {Ibaraki}},
type = {{EGRES Quick-Proof}},
url = {http://bolyai.cs.elte.hu/egres/www/qp-09-01.html},
year = {2009},
bdsk-url-1 = {http://bolyai.cs.elte.hu/egres/www/qp-09-01.html}}
@article{kt-decnt-18,
author = {Kawarabayashi, {Ken-ichi} and Thorup, Mikkel},
date-added = {2021-06-28 16:19:04 -0500},
date-modified = {2021-06-28 16:19:04 -0500},
doi = {10.1145/3274663},
journal = {J. ACM},
number = {1},
pages = {4:1--4:50},
title = {Deterministic Edge Connectivity in Near-Linear Time},
volume = {66},
year = {2018},
bdsk-url-1 = {https://doi.org/10.1145/3274663}}
@inproceedings{m-ncpef-13,
author = {M{\k a}dry, Aleksander},
booktitle = {Proc. 54th IEEE Symp. Found. Comput. Sci.},
date-added = {2021-06-28 16:18:11 -0500},
date-modified = {2021-06-28 16:18:45 -0500},
doi = {10.1109/FOCS.2013.35},
pages = {253--262},
title = {Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back},
year = {2013},
bdsk-url-1 = {https://doi.org/10.1109/FOCS.2013.35}}
@inproceedings{ls-pfmlp-14,
author = {Lee, Yin Tat and Sidford, Aaron},
booktitle = {Proc. 55th IEEE Symp. Found. Comput. Sci.},
date-added = {2021-06-28 16:17:40 -0500},
date-modified = {2021-06-28 16:17:48 -0500},
doi = {10.1109/FOCS.2014.52},
pages = {424--433},
title = {Path Finding Methods for Linear Programming: Solving Linear Programs in {\~{O}}(vrank) Iterations and Faster Algorithms for Maximum Flow},
year = {2014},
bdsk-url-1 = {https://doi.org/10.1109/FOCS.2014.52}}
@article{bgh-ruip-87,
author = {Byrd, R. H. and Goldman, A. J. and Heller, Miriam},
date-added = {2019-09-13 15:52:24 -0500},
date-modified = {2019-09-13 15:53:29 -0500},
doi = {10.1287/opre.35.1.140},
journal = {Oper. Res.},
number = {1},
pages = {140--142},
title = {Recognizing Unbounded Integer Programs},
volume = {35},
year = {2987},
bdsk-url-1 = {https://doi.org/10.1287/opre.35.1.140}}
@misc{ks-mfupg-19,
arxiv = {1907.02274},
author = {Karczmarz, Adam and Sankowski, Piotr},
date-added = {2019-08-21 10:33:44 -0500},
date-modified = {2019-08-21 10:34:20 -0500},
howpublished = {Preprint},
month = {July},
title = {Min-Cost Flow in Unit-Capacity Planar Graphs},
year = {2019}}
@inproceedings{ko-rscdpgrip-91,
author = {Kodialam, Muralidharan and Orlin, James B.},
booktitle = {Proc. 2nd Ann. ACM-SIAM Symp. Discrete Algorithms},
date-added = {2018-07-01 22:45:06 +0000},
date-modified = {2018-07-01 22:45:51 +0000},
pages = {131--135},
title = {Recognizing Strong Connectivity in (Dynamic) Periodic Graphs and Its Relation to Integer Programming},
year = {1991}}
@incollection{o-spdg-84,
author = {Orlin, James B.},
booktitle = {Progress in Combinatorial Optimization},
date-added = {2018-07-01 22:18:03 +0000},
date-modified = {2018-07-01 22:20:09 +0000},
editor = {Pulleyblank, William R.},
pages = {273--294},
publisher = {Academic Press},
title = {Some problems on dynamic/periodic graphs},
year = {1984}}
@article{fhl-iaamw-08,
author = {Feige, Uriel and Hajiaghayi, MohammadTaghi and Lee, James R.},
date-added = {2018-06-29 18:14:51 +0000},
date-modified = {2018-06-29 18:15:56 +0000},
journal = {SIAM J. Comput.},
number = {2},
pages = {629--657},
title = {Improved Approximation Algorithms for Minimum Weight Vertex Separators},
volume = {38},
year = {2008}}
@article{a-aat-10,
author = {Amir, Eyal},
date-added = {2018-06-29 18:12:19 +0000},
date-modified = {2018-06-29 18:13:37 +0000},
doi = {10.1007/s00453-008-9180-4},
journal = {Algorithmica},
number = {4},
pages = {448--479},
title = {Approximation algorithms for treewidth},
volume = {56},
year = {2010},
bdsk-url-1 = {https://doi.org/10.1007/s00453-008-9180-4}}
@article{bghk-atpfm-05,
author = {Bodlaender, Hans L. and Gilbert, John R. and Hafsteinson, Hj{\'a}lm{\'y}tr and Kloks, Ton},
date-added = {2018-06-29 17:54:00 +0000},
date-modified = {2018-06-29 17:56:23 +0000},
doi = {10.1006/jagm.1995.1009},
journal = {J. Algorithms},
number = {2},
pages = {238--255},
title = {Approximating treewidth, pathwidth, frontsize, and shortest elimination treehortest Elimination Tree},
volume = {18},
year = {2005},
bdsk-url-1 = {https://doi.org/10.1006/jagm.1995.1009}}
@inproceedings{bddfl-5at-13,
arxiv = {1304.6321},
author = {Bodlaender, Hans L. and Drange, P{\aa}l Gr{\o}n{\aa}s and Dregi, Markus S. and Fomin, Fedor V. and Lokshtanov, Daniel and Pilipczuk, Micha{\l}},
booktitle = {Proc. 54th Ann. IEEE Symp. Found. Comput.},
date-added = {2018-06-29 17:14:34 +0000},
date-modified = {2018-06-29 18:09:50 +0000},
doi = {10.1109/FOCS.2013.60},
pages = {499--508},
title = {A {$c^kn$} 5-Approximation Algorithm for Treewidth},
year = {2013},
bdsk-url-1 = {https://doi.org/10.1109/FOCS.2013.60}}
@article{b-ltaft-96,
author = {Bodlaender, Hans L.},
date-added = {2018-06-29 16:34:58 +0000},
date-modified = {2018-06-29 17:14:07 +0000},
doi = {10.1137/S0097539793251219},
journal = {SIAM J. Comput.},
number = {6},
pages = {1305--1317},
title = {A linear-time algorithm for finding tree-decompositions of small treewidth},
volume = {25},
year = {1996},
bdsk-url-1 = {https://doi.org/10.1137/S0097539793251219}}
@article{acp-cfek-87,
author = {Arnborg, Stefan and Corneil, Derek G. and Proskurowski, Andrzej},
date-added = {2018-06-29 16:31:46 +0000},
date-modified = {2018-06-29 17:14:26 +0000},
journal = {SIAM J. Alg. Discrete Methods},
number = {2},
pages = {277--284},
title = {Complexity of finding embeddings in a $k$-tree},
volume = {8},
year = {1987}}
@article{hp-lbdpp-02,
author = {van der Holst, Hein and de Pina, Jos{\'{e}} Coelho},
date-added = {2017-10-13 11:41:24 +0000},
date-modified = {2017-10-13 11:41:59 +0000},
doi = {10.1016/S0166-218X(01)00294-3},
journal = {Discrete Appl. Math.},
number = {1--3},
pages = {251--261},
title = {Length-bounded disjoint paths in planar graphs},
volume = {120},
year = {2002},
bdsk-url-1 = {https://doi.org/10.1016/S0166-218X(01)00294-3}}
@article{j-nmmpo-62,
author = {Jewell, William S.},
date-added = {2017-10-11 20:21:09 +0000},
date-modified = {2017-10-11 20:22:36 +0000},
doi = {10.1287/opre.10.4.476},
journal = {Oper. Res.},
keywords = {successive shortest paths},
number = {4},
pages = {476--499},
read = {1},
title = {New Methods in Mathematical Programming: {O}ptimal Flow Through Networks with Gains},
volume = {10},
year = {1962},
bdsk-url-1 = {http://dx.doi.org/10.1287/opre.10.4.476}}
@article{ho-fafmd-94,
author = {Hao, Jianxiu and Orlin, James B.},
date-added = {2017-10-08 20:48:19 +0000},
date-modified = {2017-10-08 20:51:32 +0000},
doi = {10.1006/jagm.1994.1043},
journal = {J. Algorithms},
number = {3},
pages = {424--446},
title = {A faster algorithm for finding the minimum cut in a directed graph},
volume = {17},
year = {1994},
bdsk-url-1 = {http://dx.doi.org/10.1006/jagm.1994.1043}}
@inproceedings{hrw-lfpfe-17,
arxiv = {1704.01254},
author = {Henzinger, Monika and Rao, Satish and Wang, Di},
booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},
date-added = {2017-10-08 20:20:39 +0000},
date-modified = {2017-10-08 20:21:51 +0000},
doi = {10.1137/1.9781611974782.125},
pages = {1919--1938},
read = {1},
title = {Local Flow Partitioning for Faster Edge Connectivity},
year = {2017},
bdsk-url-1 = {http://dx.doi.org/10.1137/1.9781611974782.125}}
@inproceedings{kt-dgmcs-15,
arxiv = {1411.5123},
author = {Kawarabayashi, Ken-ichi and Thorup, Mikkel},
booktitle = {Proc. 47th Ann. ACM Symp. Theory Comput.},
date-added = {2017-10-08 20:18:11 +0000},
date-modified = {2017-10-08 20:23:15 +0000},
doi = {10.1145/2746539.2746588},
pages = {665--674},
title = {Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time},
year = {2015},
bdsk-url-1 = {http://dx.doi.org/10.1145/2746539.2746588}}
@article{bkmnw-msmsm-17,
author = {Borradaile, Glencora and Klein, Philip N. and Mozes, Shay and Nussbaum, Yahav and Wulff-Nilsen, Christian},
date-added = {2017-10-08 19:53:43 +0000},
date-modified = {2017-10-08 19:54:18 +0000},
doi = {10.1137/15M1042929},
journal = {SIAM J. Comput.},
number = {4},
pages = {1280--1303},
read = {1},
title = {Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time},
volume = {46},
year = {2017},
bdsk-url-1 = {https://doi.org/10.1137/15M1042929}}
@article{bv-scprw-04,
author = {Bertsimas, Dimitris and Vempala, Santosh},
date-added = {2017-08-10 17:55:29 +0000},
date-modified = {2017-08-10 17:57:07 +0000},
doi = {10.1145/1008731.1008733},
journal = {J. ACM},
keywords = {approximate centroid},
number = {4},
pages = {540--556},
read = {1},
title = {Solving convex programs by random walks},
volume = {51},
year = {2004},
bdsk-url-1 = {http://dx.doi.org/10.1145/1008731.1008733}}
@article{cm-spadc-93,
author = {Cohen, Edith and Megiddo, Nimrod},
date-added = {2017-08-10 16:05:45 +0000},
date-modified = {2017-08-10 16:06:08 +0000},
doi = {10.1145/153724.153727},
journal = {J. Assoc. Comput. Mach.},
keywords = {multidimensional parametric search},
number = {4},
pages = {791--830},
read = {1},
title = {Strongly polynomial-time and {NC} algorithms for detecting cycles in periodic graphs},
volume = {40},
year = {1993},
bdsk-url-1 = {http://dx.doi.org/10.1145/153724.153727}}
@inproceedings{ks-dcdgp-88,
author = {Kosaraju, S. Rao and Sullivan, Gregory F.},
booktitle = {Proc. 20th ACM Symp. Theory. Comput.},
date-added = {2017-08-10 15:54:10 +0000},
date-modified = {2017-08-10 15:55:58 +0000},
doi = {10.1145/62212.62251},
pages = {398--406},
title = {Detecting cycles in dynamic graphs in polynomial time (preliminary version)},
year = {1988},
bdsk-url-1 = {http://dx.doi.org/10.1145/62212.62251}}
@article{krt-fdmfa-94,
author = {King, Valerie and Rao, Satish and Tarjan, Robert E.},
date-added = {2016-11-22 16:49:55 +0000},
date-modified = {2016-11-22 16:49:55 +0000},
journal = {J. Algorithms},
number = {3},
pages = {447--474},
title = {A faster deterministic maximum flow algorithm},
volume = {17},
year = {1994}}
@inproceedings{bkmnw-msmsm-11,
author = {Borradaile, Glencora and Klein, Philip N. and Mozes, Shay and Nussbaum, Yahav and Wulff-Nilsen, Christian},
booktitle = {Proc. 52nd IEEE Symp. Found. Comput. Sci.},
date-added = {2016-11-22 16:49:55 +0000},
date-modified = {2016-11-22 16:49:55 +0000},
pages = {170--179},
title = {Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time},
year = {2011}}
@inproceedings{cns-medpk-13,
author = {Chekuri, Chandra and Naves, Guyslain and Shepherd, F. Bruce},
booktitle = {Proc. 40th Int. Colloq. Automata Lang. Prog.},
date-added = {2016-11-22 16:49:55 +0000},
date-modified = {2016-11-22 16:49:55 +0000},
pages = {328--339},
title = {Maximum Edge-Disjoint Paths in $k$-Sums of Graphs},
year = {2013}}
@article{k-rscfn-99,
abstract = {We use random sampling as a tool for solving undirected graph problems. We show that the sparse graph, or skeleton, that arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph with high probability. This makes sampling effective for problems involving cuts in graphs. We present fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding minimum cuts and maximum flows in unweighted, undirected graphs. Our cut-approximation algorithms extend unchanged to weighted graphs while our weighted-graph flow algorithms are somewhat slower. Our approach gives a general paradigm with potential applications to any packing problem. It has since been used in a near-linear time algorithm for finding minimum cuts, as well as faster cut and flow algorithms. Our sampling theorems also yield faster algorithms for several other cut-based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our methods also improve the efficiency of some parallel cut and flow algorithms. Our methods also apply to the network design problem, where we wish to build a network satisfying certain connectivity requirements between vertices. We can purchase edges of various costs and wish to satisfy the requirements at minimum total cost. Since our sampling theorems apply even when the sampling probabilities are different for different edges, we can apply randomized rounding to solve network design problems. This gives approximation algorithms that guarantee much better approximations than previous algorithms whenever the minimum connectivity requirement is large. As a particular example, we improve the best approximation bound for the minimum k-connected subgraph problem from 1.85 to 1 + O(√log n)/k).},
author = {Karger, David R.},
copyright = {Copyright {\copyright} 1999 INFORMS},
date-added = {2016-11-22 16:49:50 +0000},
date-modified = {2016-11-22 16:49:50 +0000},
issn = {0364765X},
journal = {Mathematics of Operations Research},
jstor_articletype = {research-article},
jstor_formatteddate = {May, 1999},
language = {English},
number = {2},
pages = {pp. 383-413},
publisher = {INFORMS},
title = {Random Sampling in Cut, Flow, and Network Design Problems},
url = {http://www.jstor.org/stable/3690490},
volume = {24},
year = {1999},
bdsk-url-1 = {http://www.jstor.org/stable/3690490}}
@inproceedings{ks-oamc-93,
author = {Karger, David R. and Stein, Clifford},
booktitle = {Proc. 25th Ann. ACM Symp. Theory Comput.},
date-added = {2016-11-22 16:49:44 +0000},
date-modified = {2016-12-02 22:55:38 +0000},
pages = {757--765},
title = {An $\tilde{O}(n^2)$ algorithm for minimum cuts},
year = {1993}}
@inproceedings{o-mfotl-13,
author = {Orlin, James B.},
booktitle = {Proc. 45th Ann. ACM Symp. Theory Comput.},
date-added = {2016-11-22 16:47:36 +0000},
date-modified = {2016-11-22 16:47:36 +0000},
pages = {765--774},
title = {Max flows in {$O(nm)$} time, or better},
year = {2013}}
@inproceedings{mmprw-fesp-05,
author = {Maggs, Bruce M. and Miller, Gary L. and Parekh, Ojas and Ravi, R. and Woo, Shan Leung Maverick},
booktitle = {Proc. 17th Ann. ACM Symp. Parallelism Alg. Arch.},
date-added = {2015-08-29 17:28:40 +0000},
date-modified = {2015-08-29 17:37:25 +0000},
pages = {176--185},
title = {Finding Effective Support-Tree Preconditioners},
year = {2005}}
@inproceedings{kosz-scass-13,
arxiv = {1301.6628},
author = {Kelner, Jonathan A. and Orecchia, Lorenzo and Sidford, Aaron and Zhu, Zeyuan Allen},
booktitle = {Proc. 45th Ann. ACM Symp. Theory Comput.},
date-added = {2015-08-29 17:24:16 +0000},
date-modified = {2015-08-29 17:25:42 +0000},
pages = {911--920},
title = {A Simple, Combinatorial Algorithm for Solving {SDD} Systems in Nearly-Linear Timeinear Time},
year = {2013}}
@phdthesis{g-cpssd-96,
author = {Gremban, Keith},
comments = {SDD to Laplacian reduction},
date-added = {2015-08-29 16:00:20 +0000},
date-modified = {2015-08-29 16:05:15 +0000},
note = {Tech. Rep. CMU-CS-96-123},
read = {1},
school = {Carnegie Mellon University},
title = {Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems},
url = {https://www.cs.cmu.edu/~glmiller/Publications/b2hd-GrembanPHD.html},
year = {1996},
bdsk-url-1 = {https://www.cs.cmu.edu/~glmiller/Publications/b2hd-GrembanPHD.html}}
@article{cct-egbep-03,
author = {Chan, Wun-Tat and Chin, Francis Y. L. and Ting, Hing-Fung},
date-added = {2015-06-29 20:09:28 +0000},
date-modified = {2015-06-29 20:10:12 +0000},
journal = {Algorithmica},
number = {4},
pages = {343--359},
title = {Escaping a grid by edge-disjoint paths},
volume = {36},
year = {2003}}
@inproceedings{cct-faffd-99,
author = {Chan, Wun-Tat and Chin, Francis Y. L. and Ting, Hing-Fung},
booktitle = {Proc. 10th Int. Symp. Algorithms Comput.},
comments = {Edge-disjoint only},
date-added = {2015-06-29 20:06:07 +0000},
date-modified = {2015-06-29 20:13:05 +0000},
pages = {399--402},
read = {1},
series = {Lecture Notes Comput. Sci.},
title = {A Faster Algorithm for Finding Disjoint Paths in Grids},
volume = {1741},
year = {1999}}
@inproceedings{hs-ebrip-97,
author = {Hershberger, John and Suri, Subhash},
booktitle = {Proc. 5th Int. Workshop Algorithms Data Struct.},
comments = {Extended abstract alsp published in Proc. 13th Symp. Comput. Geom., 460--462, 1997.},
date-added = {2015-06-29 19:58:01 +0000},
date-modified = {2015-06-29 20:05:29 +0000},
pages = {462--471},
series = {Lecture Notes Comput. Sci.},
title = {Efficient breakout routing in printed circuit boards},
volume = {1272},
year = {1997}}
@inproceedings{cc-eaffd-97,
author = {Chan, Wun-Tat and Chin, Francis Y. L.},
booktitle = {Proc. 8th Ann. ACM-SIAM Symp. Discrete Algorithms},
date-added = {2015-06-29 19:54:15 +0000},
date-modified = {2015-06-29 19:56:11 +0000},
note = {Preliminary version of \cite{cc-eafft-00}},
pages = {454--463},
title = {Efficient Algorithms for Finding Disjoint Paths in Grids (Extended Abstract)},
year = {1997}}
@article{cc-eafft-00,
author = {Chan, Wun-Tat and Chin, Francis Y. L.},
comments = {maximum number of (edge- or vertex-) disjoint paths from N sources to N targets in an infinite square grid in O(N^{2.5}) time},
date-added = {2015-06-29 19:47:01 +0000},
date-modified = {2015-06-29 20:13:58 +0000},
journal = {J. Algorithms},
note = {Full version of \cite{cc-eaffd-97}},
pages = {337--369},
title = {Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids},
volume = {34},
year = {2000}}
@misc{km-oapg-13,
author = {Klein, Philip and Mozes, Shay},
date-added = {2013-11-08 19:43:01 +0000},
date-modified = {2013-11-08 19:43:57 +0000},
howpublished = {Textbook draft},
title = {Optimization Algorithms for Planar Graphs},
url = {http://planarity.org},
year = {2013},
bdsk-url-1 = {http://planarity.org}}
@article{a-ptase-98,
author = {Arora, Sanjeev},
date-added = {2013-11-08 06:46:55 +0000},
date-modified = {2013-11-08 06:47:30 +0000},
journal = {J. ACM},
number = {5},
pages = {753--782},
title = {Polynomial-time approximation schemes for {E}uclidean {TSP} and other geometric problems},
volume = {45},
year = {1998},
bdsk-url-1 = {http://dx.doi.org/10.1109/SFCS.1996.548458}}
@inproceedings{agkkw-ptasw-98,
author = {Arora, Sanjeev and Grigni, Michelangelo and Karger, David R. and Klein, Philip N. and Woloszyn, Andrzej},
booktitle = {Proc. 9th ACM-SIAM Symp. Discrete Algorithms},
date-added = {2013-11-08 06:45:19 +0000},
date-modified = {2013-11-08 06:46:42 +0000},
pages = {33--41},
title = {A polynomial-time approximation scheme for weighted planar graph {TSP}},
year = {1998}}
@inproceedings{bg-mw2ec-07,
author = {Berger, Andr{\'e} and Grigni, Michelangelo},
booktitle = {Proc. 34th Int. Colloq. Automata Lang. Program.},
date-added = {2013-11-08 06:43:08 +0000},
date-modified = {2013-11-08 06:44:36 +0000},
doi = {10.1007/978-3-540-73420-8_10},
editor = {Arge, Lars and Cachin, Christian and Jurdzinski, Tomasz and Tarlecki, Andrzej},
owner = {glencora},
pages = {90--101},
publisher = {Springer},
series = {Lecture Notes Comput. Sci.},
timestamp = {2007.09.20},
title = {Minimum weight 2-edge-connected spanning subgraphs in planar graphs},
volume = {4596},
year = {2007},
bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-540-73420-8_10}}
@inproceedings{ckmn-aflpo-01,
author = {Charikar, Moses and Khuller, Samir and Mount, David M. and Narasimhan, Giri},
booktitle = {Proc. 12th Ann. ACM-SIAM Symp. Discrete Algorithms.},
date-added = {2013-11-08 06:41:06 +0000},
date-modified = {2013-11-08 06:42:00 +0000},
pages = {642--651},
title = {Algorithms for facility location problems with outliers},
year = {2001},
bdsk-url-1 = {http://dl.acm.org/citation.cfm?id=365411.365555}}
@inproceedings{gkp-aspgt-95,
author = {Grigni, Michelangelo and Koutsoupias, Elias and Papadimitriou, Christos H.},
booktitle = {Proc. 36th Ann. Symp. Found. Comput. Sci.},
date-added = {2013-11-08 06:37:05 +0000},
date-modified = {2013-11-08 06:39:27 +0000},
pages = {640--645},
title = {An approximation scheme for planar graph {TSP}},
year = {1995}}
@article{kr-nltas-07,
author = {Kolliopoulos, Stavros G. and Rao, Satish},
date-added = {2013-11-08 06:35:43 +0000},
date-modified = {2013-11-08 06:36:36 +0000},
journal = {SIAM J. Computing},
number = {3},
pages = {757--782},
title = {A nearly linear-time approximation scheme for the {E}uclidean k-median problem},
volume = {37},
year = {2007}}
@article{ov-faccf-13,
author = {Orlin, James B. and Vaidyanathan, Balachandran},
comments = {min-cost flow in trees in O(n log n) time},
date-added = {2013-11-08 06:29:36 +0000},
date-modified = {2013-11-08 06:31:15 +0000},
journal = {Networks},
number = {4},
pages = {288--296},
title = {Fast Algorithms for Convex Cost Flow Problems on Circles, Lines, and Trees},
volume = {62},
year = {2013}}
@inproceedings{fmps-sscsp-13,
author = {Fox-Epstein, Eli and Mozes, Shay and Phothilimthana, Phitchaya Mangpo and Sommer, Christian},
booktitle = {Proc. 14th Workshop Algorithm Engin. Exper.},
date-added = {2013-11-04 21:20:02 +0000},
date-modified = {2013-11-04 21:22:11 +0000},
keywords = {code},
pages = {26-40},
title = {Short and Simple Cycle Separators in Planar Graphs},
year = {2013}}
@article{ww-ltaed-95,
author = {Wagner, Dorthea and Weihe, Karsten},
comments = {given k pairs of terminals, find k edge-disjoint paths connecting them},
date-added = {2013-11-04 03:02:33 +0000},
date-modified = {2013-11-04 03:04:46 +0000},
journal = {Combinatorica},
keywords = {Okamura-Seymour Theorem},
number = {1},
pages = {135--150},
title = {A linear-time algorithm for edge-diosjoint paths in planar graphs},
volume = {15},
year = {1995}}
@inproceedings{kks-lsado-11,
author = {Kawarabayashi, {Ken-ichi} and Klein, Philip N. and Sommer, Christian},
booktitle = {Proc. 38th Int. Colloq. Automata Lang. Prog.},
date-added = {2013-11-04 02:05:35 +0000},
date-modified = {2013-11-04 02:06:54 +0000},
numpages = {12},
pages = {135--146},
publisher = {Springer-Verlag},
series = {Lecture Notes Comput. Sci.},
title = {Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs},
volume = {6755},
year = {2011},
bdsk-url-1 = {http://dl.acm.org/citation.cfm?id=2027127.2027142}}
@inproceedings{kt-mkcbs-11,
author = {Kawarabayashi, Ken-ichi and Thorup, Mikkel},
booktitle = {Proc. 52nd Ann. IEEE Sympos. Found. Comput. Sci.},
date-added = {2013-11-04 02:05:35 +0000},
date-modified = {2013-11-04 02:05:53 +0000},
ee = {http://dx.doi.org/10.1109/FOCS.2011.53},
pages = {160-169},
title = {The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable},
year = {2011}}
@article{bhm-assfp-11,
author = {Bateni, MohammadHossein and Hajiaghayi, MohammadTaghi and Marx, D{\'a}niel},
date-added = {2013-11-04 02:03:37 +0000},
date-modified = {2013-11-04 02:07:56 +0000},
journal = {J. ACM},
number = {5},
pages = {Article 21},
title = {Approximation Schemes for {S}teiner Forest on Planar Graphs and Graphs of Bounded Treewidth},
volume = {58},
year = {2011}}
@inproceedings{mp-lmfap-10,
arxiv = {1211.2189},
author = {Matouschke, Jannik and Peis, Britta},
booktitle = {Proc. 36th Int. Workshop Graph Theor. Concepts Comput. Sci.},
date-added = {2013-11-03 22:34:44 +0000},
date-modified = {2013-11-03 22:39:29 +0000},
editor = {Thilikos, Dimitrios M.},
number = {6410},
pages = {324--335},
publisher = {Springer},
series = {Lecture Notes Comput. Sci.},
title = {Lattices and Maximum Flow Algorithms in Planar Graphs},
year = {2010}}
@article{f-lsfpg-04,
author = {Felsner, Stefan},
date-added = {2013-11-03 22:30:46 +0000},
date-modified = {2013-11-03 22:31:34 +0000},
journal = {Elec. J. Combin.},
keywords = {Eulerian orientations, spanning trees, Schnyder woods},
number = {1},
pages = {R15},
title = {Lattie structures from planar graphs},
volume = {11},
year = {2004}}
@inproceedings{atz-ietsp-03,
author = {Arge, Lars and Toma, Laura and Zeh, Norbert},
booktitle = {Proc. 15th Ann. ACM Symp. Parallel Algorithms Arch.},
date-added = {2013-11-03 22:18:15 +0000},
date-modified = {2013-11-03 22:19:59 +0000},
keywords = {breadth-first search, single-source shortest paths},
pages = {85--93},
title = {{I/O}-efficient topological sorting of planar {DAGs}},
year = {2003}}
@article{t-usspw-99,
author = {Thorup, Mikkel},
date-added = {2013-11-03 22:14:20 +0000},
date-modified = {2013-11-03 22:15:18 +0000},
journal = {J. ACM},
number = {3},
pages = {362--394},
title = {Undirected single-source shortest paths with positive integer weights in linear time},
volume = {46},
year = {1999}}
@article{bt-fmmfs-93,
author = {Booth, Heather and Tarjan, Robert E.},
comments = {$O(m \log m)$ time},
date-added = {2013-11-02 17:37:39 +0000},
date-modified = {2013-11-04 21:01:29 +0000},
journal = {J. Algorithms},
number = {3},
pages = {416--446},
read = {1},
title = {Finding the minimum-cost maximum flow in a series-parallel network},
volume = {15},
year = {1993}}
@unpublished{v-pma-14,
author = {Vazirani, Vijay V.},
date-added = {2013-11-02 12:54:17 +0000},
date-modified = {2014-05-01 14:38:28 +0000},
month = {March},
note = {Unpublished manuscript},
title = {A Proof of the {MV} Matching Algorithm},
url = {http://www.cc.gatech.edu/~vazirani/new-proof.pdf},
year = {2014},
bdsk-url-1 = {http://www.cc.gatech.edu/~vazirani/new-proof.pdf}}
@article{ce-focmf-13,
author = {Chambers, Erin Wolf and Eppstein, David},
date-added = {2013-11-02 12:12:00 +0000},
date-modified = {2017-10-08 20:02:17 +0000},
doi = {10.7155/jgaa.00291},
journal = {J. Graph Algorithms Appl.},
number = {3},
pages = {201--220},
read = {1},
title = {Flows in One-Crossing-Minor-Free Graphs},
volume = {17},
year = {2013},
bdsk-url-1 = {http://dx.doi.org/10.7155/jgaa.00291}}
@article{cm-appam-89,
author = {Cheriyan, Joseph and Maheshwari, S. N.},
date-added = {2013-10-30 21:15:22 +0000},
date-modified = {2013-10-30 21:16:00 +0000},
journal = {SIAM J. Comput.},
number = {6},
pages = {1057--1086},
title = {Analysis of Preflow Push Algorithms for Maximum Network Flow},
volume = {18},
year = {1989}}
@article{cm-ahsrp-99,
author = {Cheriyan, Joseph and Mehlhorn, Kurt},
date-added = {2013-10-30 21:13:34 +0000},
date-modified = {2013-10-30 21:14:26 +0000},
journal = {Inf. Proc. Letters},
number = {5},
pages = {239--242},
title = {An analysis of the highest-level selection rule in the preflow-push max-flow algorithm},
volume = {69},
year = {1999}}
@inproceedings{ms-edopg-12,
arxiv = {1011.5549},
author = {Mozes, Shay and Sommer, Christian},
booktitle = {Proc. 23rd Ann. ACM-SIAM Symp. Discrete Algorithms},
date-added = {2013-10-30 15:43:45 +0000},
date-modified = {2013-10-30 20:16:04 +0000},
pages = {209--222},
read = {1},
title = {Exact distance oracles for planar graphs},
year = {2012}}
@article{akmsw-gamsa-87,
author = {Aggarwal, Alok and Klawe, Maria M. and Moran, Shlomo and Shor, Peter and Wilber, Robert},
date-added = {2013-10-30 15:40:16 +0000},
date-modified = {2023-03-10 16:02:38 -0600},
doi = {10.1007/BF01840359},
journal = {Algorithmica},
keywords = {SMAWK},
number = {1--4},
pages = {195--208},
title = {Geometric applications of a matrix-searching algorithm},
volume = {2},
year = {1987},
bdsk-url-1 = {https://doi.org/10.1007/BF01840359}}
@inproceedings{akmsw-gamsa-86,
author = {Aggarwal, Alok and Klawe, Maria and Moran, Shlomo and Shor, Peter W. and Wilber, Robert},
booktitle = {Proc. 2nd Ann. Symp. Comput. Geom.},
date-added = {2013-10-30 15:38:17 +0000},
date-modified = {2013-10-30 15:42:01 +0000},
keywords = {SMAWK},
pages = {285--292},
title = {Geometric applications of a matrix searching algorithm},
year = {1986}}
@inproceedings{bhpt-tgtca-07,
author = {Bhalgat, Anand and Hariharan, Ramesh and Panigrahi, Debmalya and Telikepalli, Kavitha},
booktitle = {Proc. 39th Ann. ACM Symp. Theory Comput.},
date-added = {2013-10-30 15:08:30 +0000},
date-modified = {2013-10-30 15:11:17 +0000},
pages = {605--614},
title = {An {$\tilde{O}(mn)$} {Gomory}-{Hu} tree construction algorithm for unweighted graphs},
year = {2007}}
@article{l-mtgt-76,
author = {Lov{\'a}sz, L{\'a}szl{\'o}},
date-added = {2013-10-30 13:13:08 +0000},
date-modified = {2013-10-30 13:13:45 +0000},
journal = {J. Comb. Theory Ser. B},
pages = {96--103},
title = {On two minimax theorems in graph theory},
volume = {21},
year = {1976}}
@article{ly-mtdg-78,
author = {Lucchesi, Cl{\'a}udio L. and Younger, Daniel H.},
date-added = {2013-10-30 13:11:27 +0000},
date-modified = {2013-10-30 13:15:36 +0000},
journal = {J. London Math. Soc., Ser. 2},
pages = {369--374},
read = {1},
title = {A minimax theorem for directed graphs},
volume = {17},
year = {1978}}
@inproceedings{bkvz-tpsga-99,
author = {Berman, Piotr and Kahng, Andrew B. and Vidhani, Devendra and Zelikovsky, Alexander},
booktitle = {Proc. 6th Int. Workshop Algorithms Data Struct.},
comments = {$O((n\log n)^{3/2}\alpha(n))$ time},
date-added = {2013-10-30 12:45:10 +0000},
date-modified = {2013-10-30 12:48:40 +0000},
editor = {Dehne, Frank and Sack, J{\"o}rg-R{\"u}diger and Gupta, Arvind and Tamassia, Roberto},
number = {1663},
pages = {25--36},
series = {Lecture Notes Comput. Sci.},
title = {The {$T$}-join Problem in Sparse Graphs: {Applications} to Phase Assignment Problem in {VLSI} Mask Layout},
year = {1999}}
@article{lp-ppgfc-12,
author = {Liers, Frauke and Pardella, Gregor},
date-added = {2013-10-30 12:06:54 +0000},
date-modified = {2013-10-30 12:43:32 +0000},
journal = {Comput. Optim. Appl.},
pages = {323--344},
title = {Partitioning planar graphs: {A} fast combinatorial approach for max-cut},
url = {http://e-archive.informatik.uni-koeln.de/605/},
year = {2012},
bdsk-url-1 = {http://e-archive.informatik.uni-koeln.de/605/}}
@article{ai-chpfm-77,
author = {Aoshima, K. and Iri, Masao},
date-added = {2013-10-30 12:00:33 +0000},
date-modified = {2013-10-30 12:01:59 +0000},
journal = {SIAM J. Comput.},
note = {Corrects minor error in \cite{h-fmpgp-75}},
number = {1},
pages = {86--87},
title = {Comments on {F.} {Hadlock's} paper: {``Finding} a maximum cut of a planar graph in polynomial time''},
volume = {6},
year = {1977}}
@article{h-fmpgp-75,
author = {Hadlock, Frank O.},
comments = {$O(n^3)$ time via Edmonds' algorithm for perfect matching},
date-added = {2013-10-30 11:52:41 +0000},
date-modified = {2013-10-30 12:02:15 +0000},
journal = {SIAM J. Comput.},
note = {Correction in \cite{ai-chpfm-77}},
number = {3},
pages = {221--225},
title = {Finding a maximum cut of a planar grph in polynomial time},
volume = {4},
year = {1975}}
@article{gt-fsagg-91,
author = {Gabow, Harold N. and Tarjan, Robert E.},
comments = {min-cost matching with integral weights in $O(\sqrt{n\alpha(m,n)\log n} m \log (nC))$},
date-added = {2013-10-30 11:44:07 +0000},
date-modified = {2013-10-30 11:46:51 +0000},
journal = {J. ACM},
number = {4},
pages = {815--853},
title = {Faster scaling algorithms for general graph matching problems},
volume = {38},
year = {1991}}
@inproceedings{b-ammgg-90,
author = {Blum, Norbert},
booktitle = {Proc. 17th Int. Colloq. Automata Lang. Prog.},
date-added = {2013-10-30 11:40:13 +0000},
date-modified = {2013-10-30 11:42:07 +0000},
editor = {Paterson, Michael S.},
number = {443},
pages = {586--597},
publisher = {Springer},
series = {Lecture Notes Comput. Sci.},
title = {A new approach to maximum macthing in general graphs},