Pascal Schweitzer
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Pascal Schweitzer has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Daniel Johannsen
Tel Aviv University
1 shared publication - Giuseppe Liotta
Department of Engineering, University of Perugia, Perugia, Italy
1 shared publication - Kurt Mehlhorn
Max Planck Institute for Informatics, Saarbrücken, Germany
1 shared publication - Momchil Rusinov
Max-Planck-Institut Für Informatik, Stuhlsatzenhausweg 85 66123 Saarbrücken, Germany
1 shared publication - Naoki Katoh
Kwansei Gakuin University
1 shared publication - Nicole Megow
University of Bremen, Bremen, Germany
1 shared publication
Latest Publications
- 29 May 2014
- Published by Springer Nature in Algorithmica
- Vol. 72 (4) , 1033-1054
A Linear-Time Algorithm for Testing Outer-1-Planarity
- 29 May 2014
- Published by Springer Nature in Algorithmica
- Vol. 72 (4) , 1033-1054
A Linear-Time Algorithm for Testing Outer-1-Planarity
- 1 December 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 463, 62-72
Online graph exploration: New results on old and new algorithms
- 1 December 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 463, 62-72
Online graph exploration: New results on old and new algorithms
- 1 November 2010
- Published by Wiley in Journal of Graph Theory
- Vol. 65 (3) , 253-261
Homomorphism–homogeneous graphs
We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–homogeneity. Further, we show that there are homomorphism–homogeneous graphs that do not contain the Rado graph as a spanning subgraph answering the second open question. We also treat the case of homomorphism–homogeneous graphs with loops allowed, showing that the corresponding decision problem is co–NP complete. Finally, we extend the list of considered morphism–types and show that the graphs for which monomorphisms can be extended to epimor‐phisms are complements of homomorphism–homogeneous graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 253–261, 2010
- 1 November 2010
- Published by Wiley in Journal of Graph Theory
- Vol. 65 (3) , 253-261
Homomorphism–homogeneous graphs
We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–homogeneity. Further, we show that there are homomorphism–homogeneous graphs that do not contain the Rado graph as a spanning subgraph answering the second open question. We also treat the case of homomorphism–homogeneous graphs with loops allowed, showing that the corresponding decision problem is co–NP complete. Finally, we extend the list of considered morphism–types and show that the graphs for which monomorphisms can be extended to epimor‐phisms are complements of homomorphism–homogeneous graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 253–261, 2010
- Open Access
Counting Defective Parking Functions
Suppose that $n$ drivers each choose a preferred parking space in a linear car park with $m$ spaces. Each driver goes to the chosen space and parks there if it is free, and otherwise takes the first available space with larger number (if any). If all drivers park successfully, the sequence of choices is called a parking function. In general, if $k$ drivers fail to park, we have a \emph{defective parking function} of \emph{defect} $k$. Let $\cp(n,m,k)$ be the number of such functions. In this paper, we establish a recurrence relation for the numbers $\cp(n,m,k)$, and express this as an equation for a three-variable generating function. We solve this equation using the kernel method, and extract the coefficients explicitly: it turns out that the cumulative totals are partial sums in Abel's binomial identity. Finally, we compute the asymptotics of $\cp(n,m,k)$. In particular, for the case $m=n$, if choices are made independently at random, the limiting distribution of the defect (the number of drivers who fail to park), scaled by the square root of $n$, is the Rayleigh distribution. On the other hand, in case $m=\omega(n)$, the probability that all spaces are occupied tends asymptotically to one.Open AccessCounting Defective Parking Functions
Suppose that $n$ drivers each choose a preferred parking space in a linear car park with $m$ spaces. Each driver goes to the chosen space and parks there if it is free, and otherwise takes the first available space with larger number (if any). If all drivers park successfully, the sequence of choices is called a parking function. In general, if $k$ drivers fail to park, we have a \emph{defective parking function} of \emph{defect} $k$. Let $\cp(n,m,k)$ be the number of such functions. In this paper, we establish a recurrence relation for the numbers $\cp(n,m,k)$, and express this as an equation for a three-variable generating function. We solve this equation using the kernel method, and extract the coefficients explicitly: it turns out that the cumulative totals are partial sums in Abel's binomial identity. Finally, we compute the asymptotics of $\cp(n,m,k)$. In particular, for the case $m=n$, if choices are made independently at random, the limiting distribution of the defect (the number of drivers who fail to park), scaled by the square root of $n$, is the Rayleigh distribution. On the other hand, in case $m=\omega(n)$, the probability that all spaces are occupied tends asymptotically to one.