Lower bounds on collective additive spanners

Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler +1

In this paper we present various lower bound results on collective tree spanners and on spanners of bounded treewidth. A graph $G$ is said to admit a system of $\hat{I}¼$ collective addi…