Quantitative characteristics of cycles and their relations with stretch and spanning tree congestion

R. Khan, Mikhail I. Ostrovskii, Lakshmi Iswara Chandra Vidyasagar, Florin Catrina, Isaac Moorman

Publication date: 15 April 2021

Abstract: The main goal of this article is to introduce new quantitative characteristics of cycles in finite simple connected graphs and to establish relations of these characteristics with the stretch and spanning tree congestion of graphs. The main new parameter is named the support number. We give a polynomial approximation algorithm for the support number with the aid of yet another characteristic we introduce, named the cycle width of the graph.

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Approximation algorithms (68W25)

This page was built for publication: Quantitative characteristics of cycles and their relations with stretch and spanning tree congestion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6365427)