Publications of András Frank

Google Scholar Citations.

Book

B1   A. Frank, Connections in Combinatorial Optimization, Oxford University Press, 2011 (ISBN 978-0-19-920527-1). Oxford Lecture Series in Mathematics and its Applications, 38.

Reviewed in: Mathematical Reviews, Zentralblatt

Papers in Journals

J1   A. Frank, On a class of balanced hypergraphs, Discrete Mathematics 20 (1977) 11-20.

J2   A. Frank, Kernel systems of directed graphs, Acta Scientiarum Mathematicarum (Szeged) 41, 1-2 (1979) 63-76.

J3   A. Frank, Covering branchings, Acta Scientiarum Mathematicarum (Szeged) 41, 1-2 (1979) 77-81.

J4   A. Frank, On the orientation of graphs, J. Combinatorial Theory, Ser. B, 28 (1980) 251-261.

J5   A. Frank, On chain and antichain families of a partially ordered set, J. Combinatorial Theory, Ser. B, 29 (1980) 176-184.

J6   A. Frank, A weighted matroid intersection algorithm, J. Algorithms 2 (1981) 328-336.

J7   A. Frank, How to make a digraph strongly connected, Combinatorica 1 (1981) 145-153.

J8   A. Frank, An algorithm for submodular functions on graphs, Annals of Discrete Mathematics 16 (1982) 97-120.

J9   A. Frank, A note on k-strongly connected orientations of an undirected graph, Discrete Mathematics 39 (1982) 103-104.

J10   A. Frank, Disjoint paths in a rectilinear grid, Combinatorica 2 (1982) 361-371. (A preliminary version entitled Disjoint paths in the plane, has appeared in: Graph Theory (Lagow, Poland 1981) Lecture Notes in Mathematics, Vol 1018 (eds. M. Borowiecki, J. W. Kennedy and M. Syslo) Springer Verlag (1983) 33-37.)

J11   A. Frank, Finding feasible vectors of Edmonds-Giles polyhedra, J. Combinatorial Theory Ser. B, 36 (1984) 221-239.

J12   A. Frank, A. Sebõ and É. Tardos, Covering directed and odd cuts , Mathematical Programming Studies 22 (1984) 99-112.

J13   A. Frank and É. Tardos, An algorithm for the unbounded matroid intersection polyhedron, Annals of Discrete Mathematics 19 (1984) 129-134.

J14   A. Frank, Edge-disjoint paths in planar graphs, J. of Combinatorial Theory, Ser. B. 39 (1985) 164-178.

J15   W. Cunningham and A. Frank, A primal-dual algorithm for submodular flows, Mathematics of Operations Research, 10 (1985) 251-261.

J16   A. Frank, On connectivity properties of Eulerian digraphs, Annals of Discrete Math. 41 (1989) 179-194 (North Holland).

J17   A. Frank and É. Tardos, Generalized polymatroids and submodular flows, Mathematical Programming, Ser. B. 42 (1988) 489-563.

J18   A. Frank and É. Tardos, An application of simultaneous diophantine approximation in combinatorial optimization, Combinatorica 7 (1987) 49-65. (A preliminary version has appeared in: Symposium on Foundations of Computer Science (1985) (26), 459-465.)

J19   A. Frank and É. Tardos, An application of submodular flows, Linear Algebra and its Applications 114/115 (1989) 329-348.

J20   H. Fleischner and A. Frank, On circuit decomposition of planar Eulerian graphs, J. Combinatorial Theory, Ser. B. 50 (1990) 245-253.

J21   A. Frank and A. Schrijver, Edge-disjoint circuits in graphs on the torus, J. Combinatorial Theory, Ser. B 55 (1992) 9-17.

J22   A. Frank, Packing paths in planar graphs, Combinatorica 10 (1990) 329-335.

J23   A. Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM J. on Discrete Math. 5 (1992), 22-53. (A preliminary version appeared in the proceedings of the FOCS meeting held in October, 1990.)

J24   A. Frank, Conservative weightings and ear-decompositions of graphs , Combinatorica, 13 (1993) 65-81 (A preliminary version appeared in IPCO, 217-230, R. Kannan and W. Pulleyblank, eds, 1990, University of Waterloo Press.)

J25   A. Frank, Submodular functions in graph theory, Discrete Mathematics, Graph Theory and Combinatorics 111 (1993) 231-243.

J26   A. Frank, On a theorem of Mader, Annals of Discrete Mathematics 101 (1992) 49-57.

J27   A. Frank, T. Ibaraki and H. Nagamochi, On sparse subgraphs preserving connectivity properties, Journal of Graph Theory 17 (1993) 275-281.

J28   A. Frank, T. Nishizeki, N. Saito, J. Suzuki and É. Tardos, Algorithms for routing around a rectangle, Discrete Applied Mathematics 40 (1992) 363-378. (A preliminary version: A. Frank and É. Tardos, On routing around a rectangle, has appeared in: Proceedings of the ETAN Network Theory Symposium, held in Yugoslavia (1984)).

J29   A. Frank and Z. Szigeti, On packing T-cuts, J. Combinatorial Theory, Ser. B 61 (1994) 263-271.

J30   J. Bang-Jensen, A. Frank and B. Jackson, Preserving and increasing local edge-connectivity in mixed graph, SIAM J. on Discrete Math. 8 (1995) 155-178.

J31   A. Frank and T. Jordán, Minimal edge-coverings of pairs of sets, J. Combinatorial Theory, Ser. B. 65 (1995) 73-110.

J32   A. Frank and Z. Szigeti, A note on packing paths in planar graphs, Mathematical Programming 70 (1995) 201-210.

J33   A. Frank, Orientations of Graphs and Submodular Flows, Congressus Numerantium 113 (1996) (A.J.W. Hilton, ed.) 111-142.

J34   A. Frank, A. Karzanov and A. Sebõ, On integer multiflow maximization, SIAM J. on Discrete Math. 10 (1997) 158-170. (A preliminary version entitled On multiflow problems appeared in the Proceedings of the second IPCO Conference, Pittsburgh, 1992.)

J35   P.L. Erdõs, A. Frank and L.A. Székely, Minimum multiway cuts in trees, Discrete Applied Mathematics 87 (1998) 67-76.

J36   A. Frank, T. Ibaraki and H. Nagamochi, Two arc-disjoint paths in Eulerian digraphs, SIAM J. on Discrete Math. 11 (1998) 557-589. (A preliminary version appeared as A. Frank, H. Nagamochi, T. Ibaraki, Two arc-disjoint paths in Eulerian di-graphs , 6'th International Symposium on Algorithms and Computation ISAAC'95, Cairns, December 1995, "Algorithms and Computation", (Eds: J. Staples, P. Eades, N. Katoh and A. Moffat), Lecture Notes in Computer Science 1004, Springer, 92-101.)

J37   A. Frank, Finding minimum generators of path systems, J. Combinatorial Theory, Ser B. 75 (1999) 237-244.

J38   A. Benczúr and A. Frank, Covering symmetric supermodular functions by graphs, in: Connectivity Augmentation of Networks: Structures and Algorithms, Mathematical Programming, (ed. A. Frank) Ser. B. 84 (1999) 483-503.

J39   A. Frank, Increasing the rooted connectivity of a digraph by one, in: Connectivity Augmentation of Networks: Structures and Algorithms, Mathematical Programming, (ed. A. Frank) Ser. B. 84 (1999) 565-576.

J40   A. Frank and T. Jordán, Directed vertex-connectivity augmentation, in: Connectivity Augmentation of Networks: Structures and Algorithms, Mathematical Programming, (ed. A. Frank) Ser. B. 84 (1999) 537-553.

J41   A. Frank and Z. Király, Graph orientations with edge-connection and parity constraints, Combinatorica 22 (2002) 47-70. (A preliminary version entitled Parity constrained k-edge-connected orientations , appeared in: Integer Programming and Combinatorial Optimization (eds., G. Cornuejols, R. Burkard, G.J. Woeginger) Springer, Lecture Notes in Computer Science 1610 (1999) 191-201.)

J42   A. Frank, T. Jordán and Z. Szigeti, An orientation theorem with parity conditions, Discrete Applied Mathematics 115 (2001) 37-47. A perliminary version appeard in: Integer Programming and Combinatorial Optimization (eds., G. Cornuejols, R. Burkard, G.J. Woeginger) Springer, Lecture Notes in Computer Science 1610 (1999) 183-190. (Proceedings of the 7th International IPCO Conference held in Graz, Austria, June 1999.)

J43   A. Frank and L. Szegõ, A note on the path-matching formula, Journal of Graph Theory 41 (2002) 110-119.

J44   A. Frank, B. Shepherd, V. Tandon and Z. Végh, Node-capacitated ring routing, Mathematics of Operations Research 27 (2002) 372-383.

J45   Frank A., A Magyar Módszer és általánosításai, Szigma, 2002, XXXIII, 1-2, 13-44. [The Hungarian Method and its extensions].

J46   Frank A., Restricted t-matchings in bipartite graphs, Submodularity, (guest editor S. Fujishige) Discrete Applied Mathematics 131 (2003) 337-346.

J47   A. Frank and T. Király, Combined connectivity augmentation and orientation problems, Submodularity, (guest editor S. Fujishige) Discrete Applied Mathematics 131 (2003) 401-419. (A preliminary version appeared in the Proceedings of the 8th IPCO Conference, (June 2001), eds. K. Aardal and B. Gerards, Springer, 130-144.)

J48   A. Frank and L. Szegõ, Constructive characterizations for packing and covering with trees, Submodularity, (guest editor S. Fujishige) Discrete Applied Mathematics 131 (2003) 347-371. (A preliminary version entitled An extension of a theorem of Henneberg and Laman appeared in the Proceedings of the 8th IPCO Conference, (June 2001), eds. K. Aardal and B. Gerards, Springer, 145-160.)

J49   A. Frank, T. Király and M. Kriesell, On decomposing a hypergraph into k connected sub-hypergraphs, Submodularity, (guest editor S. Fujishige) Discrete Applied Mathematics 131 (2003) 373-383.

J50   A. Frank, T. Király and Z. Király, On the orientation of graphs and hypergraphs, Submodularity, (guest editor S. Fujishige) Discrete Applied Mathematics 131 (2003) 385-400.

J51   T. Fleiner, A. Frank and S. Iwata, A constrained independent set problem for matroids, Operations Research Letters 32 (2004) 23-26.

J52   M. Bárász, J. Becker and A. Frank, An algorithm for source location in directed graphs, Operations Research Letters 33 (2005) 221-230.

J53   A. Frank, On Kuhn's Hungarian Method -- a tribute from Hungary, Naval Research Logistic 52 (2005) 2-5.

J54   A. Frank, Z. Király and B. Kotnyek, An algorithm for node-capacitated ring routing, Operations Research Letters 35 (2007) 385-391. A preliminary version appeared in: Algorithms -- ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, 2005, (Eds.: G.S. Brodal, S. Leonardi), Springer, 249-258.

J55   A. Frank, L.C. Lau and J. Szabó, A note on degree-constrained subgraphs, Discrete Mathematics 308 (2008) 2647-2648.

J56   A. Frank and L. Végh, An algorithm to increase the node-connectivity of a digraph by one, Discrete Optimization 5 (2008) 677-684.

J57   A. Frank, Összefüggések a kombinatorikus optimalizálásban I. Optimalizálás gráfokon, Matematikai Lapok, (Connections in combinatorial optimization: I. Optimization on graphs, in Hungarian), 1 (2008) 20-76.

J58   A. Frank, Összefüggések a kombinatorikus optimalizálásban II. Szubmoduláris optimalizálás és poliéderes kombinatorika, Matematikai Lapok, (Connections in combinatorial optimization: II. Submodular optimization and polyhedral combinatorics, in Hungarian), 2 (2008) 14-75.

J59   A. Frank, Rooted k-connections in digraphs, Discrete Applied Mathematics 157 (2009) 1242-1254.

J60   K. Bérczi and A. Frank, Packing arborescences, Lecture Notes, RIMS Kokyuroku Bessatsu B23: Combinatorial Optimization and Discrete Algorithms, ed. S. Iwata, December 2010, 1-31.

J61   T. Fleiner and A. Frank, Balanced list edge-colourings of bipartite graphs, Electronic Notes in Discrete Mathematics, 36, (2010) 837-842.

J62   A. Frank and Z. Miklós, Push-relabel algorithms for matroids and submodular flows, Japanese Journal of Industrial and Applied Mathematics 29 (3) (2012), 419-439.

J63   A. Frank, S. Fujishige, N. Kamiyama, N. Katoh, Independent arborescences in directed graphs, Discrete Mathematics 313 (4) (2013), 453-459.

J64   A. Frank and Cs. Király, Tree-compositions and orientations, Operations Research Letters 41 (4) (2013), 336-342.

J65   A. Frank, T. Király, J. Pap and D. Pritchard, Characterizing and recognizing generalized polymatroids, Mathematical Programming, Volume 146, Issue 1-2 (2014), 245-273.

J66   D. Erdős, A. Frank, K. Kun, Sink-stable sets of digraphs, SIAM J. Discrete Math., 28(4) (2014), 1651-1674.

Conference Proceedings

P1   A. Frank, Some polynomial algorithms for certain graphs and hypergraphs, in: Proceedings of the Fifth British Combinatorial Conference, (1975) Congressus Numerantium XV, Eds. C. Nash-Williams and J. Sheehan, 211-226.

P2   A. Frank and A. Gyárfás, How to orient the edges of a graph, in: Combinatorics, (Keszthely 1976), Coll. Math. Soc. J. Bolyai 18, 353-364, North-Holland.

P3   A. Frank and A. Gyárfás, Directed graphs and computer programs, in: Problemes Combinatoires et Theorie des Graphes (1978) 157-158.

P4   A. Frank, On disjoint trees and arborescences, in: Algebraic Methods in Graph Theory, Colloquia Mathematica Soc. J. Bolyai, 25 (1978) 159-169. North-Holland.

P5   A. Frank and É. Tardos, Matroids from crossing families, in: Finite and infinite sets (Eger 1981), Colloquia Mathematica Soc. J. Bolyai, 37, (295-304) North-Holland.

P6   A. Frank, Generalized polymatroids, in: Finite and infinite sets (Eger 1981), Colloquia Mathematica Soc. J. Bolyai, 37, 285-294 North-Holland.

P7   A. Frank, P. Lévai, J. Mózes, P. Scsaurszki and É. Tardos, Sufficient condition for solvability of channel routing problems, in: IEEE Intern. Symp. on Circuits and Systems Proceedings, (Montreal 1984) 1459-1461.

P8   A. Frank, On disjoint homotopic paths in the plane, in: Polyhedral Combinatorics, eds. : W. Cook and P. D. Seymour, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1 (1990), 163-170.

P9   A. Frank and A. Schrijver, Vertex-disjoint simple paths of given homotopy in a planar graph, in: Polyhedral Combinatorics, eds.: W. Cook and P. D. Seymour, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1. 1990, 139-161.

P10   A. Frank and T. Jordán, Circuit representing trees, Graph Structure Theory, Contemporary Mathematics, Vol. 147 (American Mathematical Society) (Eds. N. Robertson, P. Seymour) 1993, 195-202.

P11   A. Frank and T. Jordán, How to make a strongly connected digraph 2-connected, in: Integer Programming and Combinatorial Optimization (Eds.: E. Balas and J. Clausen) Lecture Notes in Computer Science, 920 Springer, 1995, 414-425,

P12   A. Frank, Finding minimum weighted generators of a path system, in: Contemporary Trends in Discrete Mathemaics ( eds.: R.L. Graham, J. Kratochvil, J. Nesetril, and F.S. Roberts), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 49 (1999) 129-138.

P13   A. Frank and L. Szegõ, An extension of a theorem of Henneberg and Laman, in: Integer Programming and Combinatorial Optimization, (Proceedings of the 8th IPCO Conference, Utrecht, the Netherlands, June 2001) eds. K. Aardal and B. Gerards, Springer, 145-159.

P14   A. Frank and T. Király, Combined connectivity augmentation and orientation problems, in: Integer Programming and Combinatorial Optimization, (Proceedings of the 8th IPCO Conference, Utrecht, the Netherlands, June 2001) eds. K. Aardal and B. Gerards, Springer, 130-144.

P15   A. Frank, Z. Király and B. Kotnyek, An algorithm for node-capacitated ring routing, Algorithms -- ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, 2005, (Eds.: G.S. Brodal, S. Leonardi), Springer, 249-258.

Surveys in Books

S1   A. Frank, Függelék, E. Lawler, Kombinatorikus Optimalizálás: hálózatok és matroidok c. könyvében (Mûszaki Kiadó, 1982), 331-358. (Appendix, to the Hungarian translation of E. Lawler, Combinatorial Optimization.)

S2   A. Frank, Submodular flows, in: Progress in Combinatorial Optimization (ed. W. Pulleyblank), Academic Press (1984) 147-165.

S3   A. Frank, Packing paths, circuits, and cuts - a survey , in: "Paths, Flows and VLSI-Layouts" (B. Korte, L. Lovász, H-J. Prömel, A. Schrijver, eds) pp. 47-100. (1990) Springer Verlag.

S4   A. Frank, Applications of submodular functions, in: Surveys in Combinatorics, London Mathematical Society Lecture Note Series 187, Cambridge Univ. Press, (Ed. K. Walker) 1993, pp. 85-136.

S5   A. Frank, Connectivity augmentation problems in network design, in: Mathematical Programming: State of the Art 1994, eds., J.R. Birge and K.G. Murty), The University of Michigan, pp. 34-63.

S6   A. Frank, Connectivity and network flows, in: Handbook of Combinatorics (eds. R. Graham, M. Grötschel and L. Lovász), Elsevier Science B.V. (1995) 111-177.

S7   A. Frank, A survey on T-joins, T-cuts, and conservative weightings, in: Combinatorics, Paul Erdõs is Eighty (Vol 2) (1996) (D. Miklós, V. T. Sós, T. Szõnyi, eds.) Bolyai Society, Mathematical Studies 2, pp. 213-252.

S8   A. Frank, Matroids and submodular functions, in: Annotated Bibliographies in Combinatorial Optimization, (M. Dell Amico, F. Maffioli, S. Martello, eds.), 1997, John Wiley, pp. 65-80.

S9   A. Frank, Applications of relaxed submodularity, in: Proceedings of the International Congress of Mathematicians, Berlin 1998, Vol. III: Invited Lectures, Documenta Mathematica, Extra Volume ICM 1998, eds. G. Fischer and U. Rehmann, pp. 343-354.

S10   A. Frank, Edge-connection of graphs, digraphs, and hypergraphs, More sets, graphs and numbers, (E. Gyõri, G. Katona, L. Lovász, eds.) Bolyai Mathematical Society Math. Studies 15, Springer Verlag, 2006, pp. 93-142.

S11   K. Bérczi and A. Frank, Variations for Lovász' submodular ideas, in: M. Grötschel, G.O.H. Katona (eds.), Building Bridges Between Mathematics and Computer Science, Bolyai Society, Series: Mathematical Studies, 19, Springer 2008, pp. 137--164.

S12   A. Frank and T. Király, A survey on covering supermodular functions, W. Cook, L. Lovász, and J. Vygen (eds.), Research Trends in Combinatorial Optimization, pp. 87-126, Springer, Berlin 2009.

S13   K. Bérczi and A. Frank, Packing arborescences, Combinatorial Optimization and Discrete Algorithms, RIMS Kokyuroku Bessatsu 23, pp. 1-31 (2010).

S14   A. Frank and T. Jordán, Graph connectivity augmentation, Krishnaiyan Thulasiraman, Subramanian Arumugam, Andreas Brandstadt, Takao Nishizeki (eds.), Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, pp. 313-346 (Chapter 14), CRC Press (2015).

Preprints Submitted for Publications

A1   K. Bérczi and A. Frank and T. Király, Supermodularity in unweighted graph optimization I: Branchings and matchings,, submitted to Mathematics of Operations Research (2016).

A2   K. Bérczi and A. Frank and T. Király, Supermodularity in unweighted graph optimization II: Matroidal term rank augmentation,, submitted to Mathematics of Operations Research (2016).

A3   K. Bérczi and A. Frank and T. Király, Supermodularity in unweighted graph optimization III: Highly-connected digraphs,, submitted to Mathematics of Operations Research (2016).

Dissertations

D1   Frank A., Kombinatórikus algoritmusok, algoritmikus bizonyítások , (Thesis for "University dr" Degree) Budapest (1975). (Combinatorial algorithms, algorithmical verifications).

D2   Frank A., Algoritmusok és minimax tételek kombinatorikus struktúrákban , (Thesis for "Candidate" Degree) Budapest (1980). (Algorithms and min-max results in combinatorial structures).

D3   Frank A., Szubmoduláris függvények a kombinatorikus optimalizálásban , (Thesis for the degree of Doctor of Sciences) (1989). (Submodular functions in combinatorial optimization).

Translations

T1   E. Lawler, Kombinatorikus Optimalizálás: hálózatok és matroidok, Mûszaki Kiadó, 1982. (Combinatorial Optimization: Networks and Matroids).

Unpublished reports

R1   J. Becker and A. Frank, A quick proof for the matroid structure of a source location problem, QP-2008-01, EGRES Quick-Proofs series, http://www.cs.elte.hu/egres (2008). See also the pages 447-448 in my book B1 above.

R2   A. Frank, On the edge-connectivity algorithm of Nagamochi and Ibaraki, Laboratorie Artemis, IMAG, Université J. Fourier, Grenoble (March 1994). For an accessible electronic version, see QP-2009-01, EGRES Quick-Proofs series, http://www.cs.elte.hu/egres (2009). See also the pages 219-221 in my book B1 above

R3   T. Fleiner and A. Frank, A quick proof for the cactus representation of mincuts, QP-2009-03, EGRES Quick-Proofs series, http://www.cs.elte.hu/egres (2009). See also the pages 230-231 in my book B1 above.