Benjamin R. Moore

activity

20232026

most citedBeyond the Pseudoforest Strong Nine Dragon Tree Theorem

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

collaborators

Showing 2024Show all

3 papers · 1 filter

math.CO2024

Smoothed analysis for graph isomorphism

Michael Anastos, Matthew Kwan, Benjamin Moore

There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial "refinement" algorithms seem to be very efficient in practice. Some philosop…

math.CO2024

An Approximate Version of the Strong Nine Dragon Tree Conjecture

Sebastian Mies, Benjamin Moore

We prove the Strong Nine Dragon Tree Conjecture is true if we replace the edge bound with $d + \big\lceil k \big\lfloor\frac{d-1}{k+1}\big\rfloor \big(\frac{d}{k+1} - \frac{1}{2} \…

math.CO2024

The Strong Nine Dragon Tree Conjecture is True for $d \leq 2 (k + 1)$

Sebastian Mies, Benjamin Moore

The arboricity $Γ (G)$ of an undirected graph $G = (V, E)$ is the minimal number $k$ such that $E$ can be partitioned into $k$ forests on $V$ . Nash-Williams' formula states that $k =…

Smoothed analysis for graph isomorphism

An Approximate Version of the Strong Nine Dragon Tree Conjecture

The Strong Nine Dragon Tree Conjecture is True for d≤2(k+1)

The Strong Nine Dragon Tree Conjecture is True for $d \leq 2 (k + 1)$