Combinatorics

Random structures

Scientific work:

Submitted papers:

[S6] Markus Kuba and Alois Panholzer. On the area under lattice paths associated with triangular diminishing urn models.
submitted.

[S5] Markus Kuba and Alois Panholzer. Enumeration results for alternating tree families.
submitted.

[S4] Svante Janson, Markus Kuba and Alois Panholzer. Generalized Stirling permutations, families of increasing trees and urn models.
submitted.

[S3] Markus Kuba and Alois Panholzer. Limiting distributions for a class of diminishing urn models.
submitted.

[S2] Markus Kuba and Alois Panholzer. A combinatorial approach to the analysis of bucket recursive trees and variants.
submitted.

[S1] Markus Kuba and Alois Panholzer. On the distribution of distances between specified nodes in increasing trees.
submitted.


Papers accepted for publication:

[A1] Alois Panholzer and Helmut Prodinger. A short proof of a series evaluation in terms of harmonic numbers.
accepted for publication in Integers: Electronic Journal of Combinatorial Number Theory.


Journal papers:

[J48] Michael Drmota, Bernhard Gittenberger, Alois Panholzer, Helmut Prodinger and Mark Ward. On the shape of the fringe of various types of random trees.
Mathematical Methods in the Applied Sciences, 32(10):1207--1245, 2009.

[J47] Cyril Banderier, Markus Kuba and Alois Panholzer. Analysis of three graph parameters for random trees.
Random Structures & Algorithms, 35:42--69, 2009.

[J46] Markus Kuba, Alois Panholzer and Helmut Prodinger. Lattice paths, sampling without replacement, and the kernel method.
Electronic Journal of Combinatorics, 16(1):paper R67, 2009.

[J45] Markus Kuba and Alois Panholzer. A combinatorial approach for analyzing the number of descendants in increasing trees and related parameters.
Quaestiones Mathematicae, 32:91--114, 2009.

[J44] Alois Panholzer. Left and right length of paths in binary trees or on a question of Knuth.
Annals of Combinatorics, 12:479--492, 2009.

[J43] Alois Panholzer and Helmut Prodinger. Bijections between certain families of labelled and unlabelled d-ary trees.
Applicable Analysis and Discrete Mathematics, 3:123--136, 2009.

[J42] Markus Kuba and Alois Panholzer. Isolating nodes in recursive trees.
Aequationes Mathematicae, 76:258--280, 2008.

[J41] Alois Panholzer. Analysis of some parameters for random nodes in priority trees.
Discrete Mathematics and Theoretical Computer Science, 10(2):1--38, 2008.

[J40] Qunqiang Feng, Hosam Mahmoud and Alois Panholzer. Limit laws for the Randić index of random binary tree models.
Annals of the Institute of Statistical Mathematics, 60:319--343, 2008.

[J39] Markus Kuba and Alois Panholzer. Isolating a leaf in rooted trees via random cuttings.
Annals of Combinatorics, 12:81--99, 2008.

[J38] Alois Panholzer. A distributional study of the path-edge covering numbers for random trees.
Discrete Applied Mathematics, 156:1036--1052, 2008.

[J37] Qunqiang Feng, Hosam Mahmoud and Alois Panholzer. Phase changes in subtree varieties in random recursive and binary search trees.
SIAM Journal on Discrete Mathematics, 22:160--184, 2008.

[J36] Markus Kuba and Alois Panholzer. On edge-weighted recursive trees and inversions in random permutations.
Discrete Mathematics, 308:529--540, 2008.

[J35] Alois Panholzer and Helmut Prodinger. The level of nodes in increasing trees revisited.
Random Structures & Algorithms, 31:203--226, 2007.

[J34] Markus Kuba and Alois Panholzer. On weighted path lengths and distances in increasing trees.
Probability in the Engineering and Informational Sciences, 21:419--433, 2007.

[J33] Markus Kuba and Alois Panholzer. On the degree distribution of the nodes in increasing trees.
Journal of Combinatorial Theory, Series A, 114:597--618, 2007.

[J32] Markus Kuba and Alois Panholzer. The left-right-imbalance of binary search trees.
Theoretical Computer Science, 370:265--278, 2007.

[J31] James Allen Fill, Nevin Kapur and Alois Panholzer. Destruction of very simple trees.
Algorithmica, 46:345--366, 2006.

[J30] Alois Panholzer. Cutting down very simple trees.
Quaestiones Mathematicae, 29:211--227, 2006.

[J29] Markus Kuba and Alois Panholzer. Descendants in increasing trees.
Electronic Journal of Combinatorics, 13(1):\#8, 2006.

[J28] Alois Panholzer and Helmut Prodinger. Computer-free evaluation of a double infinite sum via Euler sums.
Seminaire Lotharingien de Combinatoire, B55a, 2005.

[J27] Alois Panholzer. Gröbner bases and the defining polynomial of a context-free grammar generating function.
Journal of Automata, Languages and Combinatorics, 10:79--97, 2005.

[J26] Alois Panholzer. The distribution of the path edge-covering numbers for random trees.
Electronic Notes in Discrete Mathematics, 19:163--169, 2005.

[J25] Alois Panholzer. The climbing depth of random trees.
Random Structures & Algorithms, 26:84--109, 2005.

[J24] Alois Panholzer, Helmut Prodinger and Marko Riedel. Measuring post-quickselect disorder.
Journal of the Iranian Statistical Society, 3:219--249, 2004.

[J23] Alois Panholzer, Helmut Prodinger and Marko Riedel. Permuting in place: Analysis of two stopping rules.
Journal of  Algorithms, 51:170--184, 2004.

[J22] Alois Panholzer and Helmut Prodinger. Analysis of some statistics for increasing tree families.
Discrete Mathematics and Theoretical Computer Science, 6:437--460, 2004.

[J21] Alois Panholzer and Helmut Prodinger. Spanning tree size in Random Binary Search Trees.
The Annals of Applied Probability, 14:718--733, 2004.

[J20] Alois Panholzer. The distribution of the size of the ancestor-tree and of the induced spanning subtree for random trees.
Random Structures & Algorithms, 25:179--207, 2004.

[J19] Alois Panholzer. Distribution of the Steiner distance in generalized $M$-ary search trees.
Combinatorics, Probability & Computing, 13:717--733, 2004.

[J18] Kate Morris, Alois Panholzer and Helmut Prodinger. Some parameters in heap ordered trees.
Combinatorics, Probability & Computing, 13:677--696, 2004.

[J17] Alois Panholzer. On generalized Fibonacci Permutations.
Journal of Information & Optimization Sciences, 24:591--610, 2003.

[J16] Alois Panholzer. The height distribution of non-crossing trees.
Ars Combinatoria, 69:19--32, 2003.

[J15] Alois Panholzer. Analysis of Multiple Quickselect variants.
Theoretical Computer Science, 302:45--91, 2003.

[J14] Alois Panholzer and Helmut Prodinger. Bijections for ternary trees and non-crossing trees.
Discrete Mathematics, 250:181--195, 2002.

[J13] Alois Panholzer and Helmut Prodinger. Binary search tree recursions with harmonic toll functions.
Journal of Computational and Applied Mathematics, 142:211--225, 2002.

[J12] Alois Panholzer and Helmut Prodinger. A generating functions proof of a curious identity.
Integers: Electronic Journal of Combinatorial Number Theory, 2: paper A06, 2002.

[J11] Alois Panholzer and Helmut Prodinger. Moments of level numbers of leaves in binary trees.
Journal of Statistical Planning and Inference, 101:267--279, 2002.

[J10] Jean-Francoir Marckert and Alois Panholzer. Noncrossing trees are almost conditioned Galton-Watson trees.
Random Structures & Algorithms, 20:115--125, 2002.

[J9] Alois Panholzer and Helmut Prodinger. Kirkman's hypothesis revisited.
Integers: Electronic Journal of Combinatorial Number Theory, 1: paper A05, 2001.

[J8] Conrado Martinez, Alois Panholzer and Helmut Prodinger. Partial match queries in relaxed multidimensional search trees.
Algorithmica, 29:181--204, 2001.

[J7] Alois Panholzer and Helmut Prodinger. Two proofs of Filipponi's formula for Lucas numbers of odd index.
The Fibonacci Quarterly, 38:165--166, 2000.

[J6] Alois Panholzer and Helmut Prodinger. An analytic approach for the analysis of rotations in fringe-balanced binary search trees.
Annals of Combinatorics, 2:173--184, 1998.

[J5] Alois Panholzer and Helmut Prodinger. A generating functions approach for the analysis of grand averages for multiple quickselect.
Random Structures & Algorithms, 13:189--209, 1998.

[J4] Alois Panholzer and Helmut Prodinger. Average case-analysis of priority trees: A structure for priority queue administration.
Algorithmica, 22:600--630, 1998.

[J3] Alois Panholzer and Helmut Prodinger. Towards a more precise analysis of an algorithm to generate binary trees: A tutorial.
The Computer Journal, 41:201--204, 1998.

[J2] Conrado Martinez, Alois Panholzer and Helmut Prodinger. On the Number of Descendants and Ascendants in Random Search Trees.
Electronic Journal of Combinatorics, 5(1):\#20, 1998.

[J1] Alois Panholzer and Helmut Prodinger. Descendants and ascendants in binary trees.
Discrete Mathematics and Theoretical Computer Science, 1:247--266, 1997.
 

Contributions in conference proceedings:

[P13] Markus Kuba and Alois Panholzer. Enumerating alternating tree families.
Discrete Mathematics and Theoretical Computer Science,
in: "Proceedings of the 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)", Proceedings AJ, 105--116, 2008.

[P12] Michael Drmota, Bernhard Gittenberger and Alois Panholzer. The degree distribution of thickened trees.
Discrete Mathematics and Theoretical Computer Science,
in: "Proceedings of the Fifth Colloquium on Mathematics and Computer Science", Proceedings AI, 149--162, 2008.

[P11] Conrado Martinez, Alois Panholzer and Helmut Prodinger. Generating random derangements.
in: "Proceedings of the Tenth ALENEX workshop and the Fifth ANALCO workshop", 234--240, SIAM, Philadelphia, 2008.

[P10] Hsien-Kuei Hwang, Markus Kuba and Alois Panholzer. Analysis of some exactly solvable diminishing urn models.
in: "The 19th International Conference on Formal Power Series and Algebraic Combinatorics", Nankai University, Tianjin, 2007.

[P9] Markus Kuba and Alois Panholzer. Analysis of the total costs for variants of the Union-Find algorithm.
Discrete Mathematics and Theoretical Computer Science,
in: "2007 International Conference on the Analysis of Algorithms", Proceedings AH, 259--268, 2007.

[P8] Markus Kuba and Alois Panholzer. Limit laws for a class of diminishing urn models.
Discrete Mathematics and Theoretical Computer Science,
in: "2007 International Conference on the Analysis of Algorithms", Proceedings AH, 341--352, 2007.

[P7] Markus Kuba and Alois Panholzer. Analysis of insertion costs in priority trees.
in: "Proceedings of the Ninth ALENEX workshop and the Fourth ANALCO workshop", 175--182, SIAM, Philadelphia, 2007.

[P6] Alois Panholzer. Left and right length of paths in binary trees. (Extended abstract).
Discrete Mathematics and Theoretical Computer Science,
in: "Proceedings of the Fourth Colloquium on Mathematics and Computer Science", Proceedings AG, 415--418, 2006.

[P5] Markus Kuba and Alois Panholzer. Analysis of label-based parameters in increasing trees.
Discrete Mathematics and Theoretical Computer Science,
in: "Proceedings of the Fourth Colloquium on Mathematics and Computer Science", Proceedings AG, 321--330, 2006.

[P4] Bernhard Gittenberger and Alois Panholzer. Some results for monotonically labelled simply generated trees.
Discrete Mathematics and Theoretical Computer Science,
in: "2005 International Conference on the Analysis of Algorithms", Proceedings AD, 173--180, 2005.

[P3] Alois Panholzer. Destruction of Recursive Trees.
in: "Proceedings of the Third Colloquium on Mathematics and Computer Science", 267--280, Birkhäuser, Basel, 2004.

[P2] Alois Panholzer. Analysis of some tree statistics.
in: "Proceedings of the Seventh Iranian Statistitical Conference", 259--288, Allameh Tabatabaie University, Teheran, 2004.

[P1] Alois Panholzer. Non-crossing trees revisited: cutting down and spanning subtrees.
Discrete Mathematics and Theoretical Computer Science,
in "Discrete Random Walks, DRW'03", Proceedings AC, 265--276, 2003.
 

Research monograph:

[M1] Alois Panholzer. Untersuchungen zur durchschnittlichen Gestalt gewisser Baumfamilien. Mit besonderer Berücksichtigung von Anwendungen in der Informatik.
Dissertationen der Technischen Universität Wien, Band 84, Österreichischer Kunst und Kulturverlag, Wien 1999. ISBN: 3-85437-176-4. ZBl.: 0923 68097


Textbook:

[B1] Michael Drmota, Bernhard Gittenberger, Günther Karigl, Alois Panholzer. Mathematik für Informatik. Berliner Studienreihe zur Mathematik. Band 17.
Heldermann Verlag, Berlin, 2007.ISBN: 978-3-88538-117-4. ZBl.: pre05169921


Scientific Talks/Poster presentations:

"Analysis of label-dependent parameters in increasing trees and generalizations" ("CanaDAM 2009: 2nd Canadian Discrete and Algorithmic Mathematics Conference" in Montreal, Canada, 26. 5. 2009.)

"Asymptotic results for the number of unsuccesful parkers in a one-way street" ("Discrete Mathematics Days 2009" in Ottawa, Canada, 22. 5. 2009.)

"Asymptotic results for the number of unsuccesful parkers in a one-way street" ("Kolkom '08: 27th Colloquium on Combinatorics" in Magdeburg, Germany, 14. 11. 2008.)

"Combinatorial Analysis of Data Structures and Tree-like Structures" (Fonds zur Förderung der wissenschaftlichen Forschung, Wien, 6. 11. 2008.)

"On a discrete parking problem" (Academia Sinica, Taipei, Taiwan, 18. 8. 2008.)

"Enumerating alternating tree families" ("FPSAC 2008: 20th International Conference on Formal Power Series and Algebraic Combinatorics" in Valparaiso - Vina del Mar, Chile, 23. 6. 2008.)

"On a discrete parking problem" ("AofA 2008: International Conference on the Analysis of Algorithms" in Maresias, Brazil, 17. 4. 2008.)

"A study of two combinatorial problems" (University of Stellenbosch, South Africa, 25. 3. 2008.)

"Limiting distribution results for a discrete parking problem" ("GOCPS 2008: 8th German Open Conference on Probability and Statistics" in Aachen, Germany, 5. 3. 2008.)

"Analysis of some exactly solvable diminishing urn models" ("Kolkom '07: 26th Colloquium on Combinatorics" in Magdeburg, Germany, 16. 11. 2007.)

"Analysis of some exactly solvable diminishing urn models" ("FPSAC 2007: 19th International Conference on Formal Power Series and Algebraic Combinatorics" in Tianjin, China, 5. 7. 2007.)

"Analysis of the total costs for variants of the Union-Find algorithm" ("AofA '07: 2007 International Conference on the Analysis of Algorithms" in Juan-les-pins, France, 20. 6. 2007.)

"Some applications of the method of moments in the analysis of algorithms" ("CanaDAM 2007: 1st Canadian Discrete and Algorithmic Mathematics Conference" in Banff, Alberta, Canada, 31 5. 2007.)

"Analysis of insertion costs in priority trees" ("ANALCO '07: Workshop on Analytic Algorithmics and Combinatorics" in New Orleans, USA, 6. 1. 2007.)

"Left and right length of paths in binary trees" ("4th Colloquium on Mathematics and Computer Science" in Nancy, France, 19. 9. 2006.)

"Some applications of generating functions for obtaining limiting distribution results in random tree models" (Academia Sinica, Taipei, Taiwan, 14. 8. 2006.)

"The left-right-imbalance of binary search trees and related questions" ("Analysis of Algorithms 2006" in Alden Biesen, Belgium, 7. 7. 2006.)

"Applications of generating functions for limiting distribution results in random tree models" ("Rhein-Main Kolloquium Stochastik" in Frankfurt, Germany, 21. 6. 2006.)

"Recent results on the analysis of increasing trees" ("Carleton Applied Probability Workshop" in Ottawa, Canada, 3. 6. 2006.)

"Increasing trees: the combinatorial approach" (Université Paris XIII, France, 11. 4. 2006.)

"Analysis of Data Structures and Tree-like Structures" (Fonds zur Förderung der wissenschaftlichen Forschung, Wien, 20. 10. 2005.)

"Label-bezogene Parameter in Increasing trees" ("16. Internationaler Kongress der Österreichischen Mathematischen Gesellschaft" in Klagenfurt, 21. 9. 2005.)

"On path covering numbers of random trees" ("The 12th International Conference on Random Structures and Algorithms" in Poznan, Poland, 4. 8. 2005.)

"Some results for monotonically labelled simply generated trees" ("International Conference on the Analysis of Algorithms" in Barcelona, Spain, 6. 6. 2005.)

"The distribution of the path edge-covering numbers for random trees"
("Second Brazilian Symposium on Graphs, Algorithms, and Combinatorics" in Angra dos Reis, Brazil, 28. 4. 2005.)

"Destruction of recursive trees" ("Third Colloquium on Mathematics and Computer Science" in Wien, 16. 9. 2004.)

"Destruction of certain tree families" ("Seventh Iranian Statistical Conference" in Teheran, Iran, 23. 8. 2004.)

"Analysis of some tree statistics" ("Seventh Iranian Statistical Conference" in Teheran, Iran, 23. 8. 2004.)

"Climbing and destroying trees" (Academia Sinica, Taipei, Taiwan, 19. 7. 2004.)

"More results on priority trees" ("Tenth Seminar on Analysis of Algorithms" in Berkeley, USA, 14. 6. 2004.)
  
"Combinatorial analysis of certain tree parameters" (University of Szeged, Hungary, 19. 4. 2004.)
  
"Discovering the beauty of Concrete Mathematics: Thanks to my advisor and mentor" (University of the Witwatersrand, Johannesburg, South Africa, 27. 2. 2004.)
  
"Distribution results for Steiner-distances in certain tree families" ("ÖMG Tagung 2003" in Bozen, Italy, 23. 9. 2003.)
  
"Non-crossing trees revisited: cutting down and spanning subtrees" ("Discrete Random Walks 2003" in Paris, France, 3. 9. 2003.)
  
"Climbing rooted trees again" (bei der "11th International Conference on Random Structures and Algorithms" in Poznan, Poland, 13. 8. 2003.)
  
"Cutting down trees revisited: a generating functions approach" ("Ninth Seminar on Analysis of Algorithms" in San Miniato, Italy, 25. 6. 2003.)
  
"Verteilungsresultate für Steiner-Distanzen in verschiedenen Baumfamilien". (Technische Universität Graz, 6. 12. 2002.)
  
"Über das asymptotische Verhalten bestimmter rekusiver Algorithmen und rekursiv beschreibbarer Größen von Bäumen". (Technische Universität Wien, 22. 11. 2002.)

"Analysis of Multiple Quickselect variants and of the Steiner distance in Search Trees -- A generating functions approach".
(University of the Witwatersrand, Johannesburg, South Africa, 27. 8. 2002.)

"About Multiple Quickselect and the Spanning Tree Size in Binary Search Trees". (Academia Sinica, Taipei, Taiwan, 10. 7. 2002.)

"About Multiple Quickselect and the Spanning Tree Size in Binary Search Trees". ("Eight Seminar on Analysis of Algorithms" in Strobl, 28. 6. 2002.)

"Kombinatorische Analyse von Algorithmen und Datenstrukturen". (Technische Universität Wien, 2001.)

"About two combinatorial problems: Height distribution of non-crossing trees and Generalized Fibonacci permutations".
(University of Versaille Saint-Quentin-En Yvelines, France, 2001.)

"More results about non-crossing trees". ("Sixth Seminar on Analysis of Algorithms" in Krynica Morska, Poland, 2000.)

"Neuere Entwicklungen auf dem Gebiet der Computeralgebra in Zusammenhang mit Hypergeometrischer Summation". (Technische Universität Wien, 1999.)

"Bivariate Generating functions and limit laws". (University of the Witwatersrand, Johannesburg, South Africa, 1999.)

"Mathematical Analysis of some Algorithms on search tree structures". (University of the Witwatersrand, Johannesburg, South Africa, 1999.)

"Kombinatorische Analyse einiger Algorithmen in Verbindung mit Suchbäumen". (Montanuniversität Leoben, 1999.)

"Average-Case Analyse von Algorithmen". (Universität Innsbruck, 1998.)

"Einige Aspekte der kombinatorischen Analyse von Algorithmen auf Suchbäumen und verwandten Strukturen". (Universität Wien, 1998.)

"Moments of level numbers of leaves in binary trees". ("4th International Conference on Lattice Path Combinatorics" in Wien, 1998.)

 

PhD students:

Markus Kuba:
PhD thesis: "Analysis of node isolation procedures and label-based parameters in tree structures", TU Wien, 2006.


Diploma students:

Silvio Dorrighi:
Masters thesis: "Analyse und Varianten von In-Situ Permutationsalgorithmen", TU Wien, 2009.

Georg Seitz:
Masters thesis: "Parking functions and generalizations", TU Wien, 2009.

Martin Heinrich:
Masters thesis: "Komplexität und Varianten von Minesweeper", TU Wien, 2006.

Konrad Podloucky:
Masters thesis: "Analysis of non-crossing trees", TU Wien, 2005.

Philipp Agy:
Masters thesis: "Analyse von Prozeduren zum Isolieren von Knoten in Zufallsbäumen", TU Wien, 2005.

Markus Kuba:
Masters thesis: "Multiple quickselect und die Steiner-Distanz in binären Suchbäumen", TU Wien, 2004.

Alexander Zapletal:
Masters thesis: "Algorithmen in der Computeralgebra für Polynomideale und -moduln", TU Wien, 2004.