Covering of Graphs of Bounded Cycolomatic Number with Preselected Paths

Christoph Geis () and Sven O. Krumke ()
Additional contact information
Christoph Geis: Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau
Sven O. Krumke: Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau

A chapter in Operations Research Proceedings 2024, 2025, pp 181-186 from Springer

Abstract: Abstract We consider a special case of the set cover problem which we call the Preselected Path Multi-Cover problem. Given a graph G with demands on the vertices as well as a family of paths on G with capacities and cost, our goal is to find a minimum-cost multisubset of these paths that cover the demands of all vertices. This problem has applications for example in software testing, where graphs of bounded cyclomatic number appear in a natural way in order to bound the software module complexity. We give a 3-approximation for this problem restricted to graphs with minimum-degree at least 2 and bounded cyclomatic number, and a 5-approximation for graphs with bounded cyclomatic number (with no restriction on the minimum degree).

Keywords: Cyclomatic Number; Covering Problem; Approximation (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-92575-7_25

Ordering information: This item can be ordered from
http://www.springer.com/9783031925757

DOI: 10.1007/978-3-031-92575-7_25

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().