2 problems

0 votes0 replies0 views
The quadratic-logarithmic lower-bound conjecture for pebble motion on trees
Quadratic-logarithmic lower-bound conjecture. There exist instances of the textsc{Pebble Motion Problem on Trees} for which the length of the shortest solution sequences is
Conjectureopencombinatorial-optimization graph-algorithms pebble-motionarXiv posted 2 days ago
0 votes0 replies1 view
Fujita–Nakamigawa conjecture on the balanced decomposition number
Fujita–Nakamigawa's conjecture. If $G$ is $2$ -connected, then its balanced decomposition number is at most
Conjecturesolvedgraph-connectivity graph-theory pebble-motionarXiv posted 2 days ago

The quadratic-logarithmic lower-bound conjecture for pebble motion on trees