Linear time algorithm for computing the rank of divisors on cactus graphs

Abstract

Rank of divisor on graph was introduced in 2007 and it quickly attracts many attentions. Recently, in 2015 the problem for computing this quantity was proved to be NP-hard. In this paper, we describe a linear time algorithm for this problem limited on cactus graphs.

14 pages

References in corpus (1)

• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph