86 citations · 243 across the 39 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.DS2023
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai
We consider the problem of comparison-sorting an -permutation that avoids some -permutation . Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak prove that when …
math.CO2023
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices
Seth Pettie, Gábor Tardos
The extremal theory of forbidden 0-1 matrices studies the asymptotic growth of the function , which is the maximum weight of a matrix wh…
cs.DS2023
Connectivity Labeling and Routing with Multiple Vertex Failures
Merav Parter, Asaf Petruschka, Seth Pettie
We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An -vertex/edge fault tolerant (-V/EFT) co…