Nicholas J. Sieger

activity

20172024

most citedMaximal Planar Subgraphs of Fixed Girth in Random Graphs

1 citations · 1 across the 5 of their papers we have counts for

collaborators

Showing 2023Show all

3 papers · 1 filter

math.CO2023

Eulerian Polynomials for Digraphs

Kyle Celano, Nicholas Sieger, Sam Spiro

Given an $n$ -vertex digraph $D$ and a labeling $σ : V (D) \to [n]$ , we say that an arc $u \to v$ of $D$ is a descent of $σ$ if $σ (u) > σ (v)$ . Foata and Zeilberger introduced a generating…

cs.DS2023

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman

Michael Levet, Puck Rombach, Nicholas Sieger

In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in $TC^{2}$ . Our approach builds on the framework of Köbler & Verbitsky (CSR 2…

cs.DS2023

Logarithmic Weisfeiler--Leman and Treewidth

Michael Levet, Puck Rombach, Nicholas Sieger

In this paper, we show that the $(3 k + 4)$ -dimensional Weisfeiler--Leman algorithm can identify graphs of treewidth $k$ in $O (lo g n)$ rounds. This improves the result of Grohe & Ver…