Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 1
Zurück zur Trefferliste

Budgeted Maximal Graph Coverage

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-6918
  • An instance of the \emph{maximum coverage} problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is specified by the nodes of a graph, while the family of covering sets is restricted to connected subgraphs. We show that on general graphs the problem is polynomial time solvable if restricted to sets of size at most~$2$, but becomes NP-hard if sets of size~$3$ are permitted. On trees, we prove polynomial time solvability if each node appears in a fixed number of sets. In contrast, if vertices are allowed to appear an unbounded number of times, the problem is NP-hard even on stars. We finally give polynomial time algorithms for special cases where the subgraphs form paths and the host graph is a line, a cycle or a star.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Sven Krumke, Madhav Marathe, Diana Poensgen, Sekharipuram S. Ravi, Hans-Christoph Wirth
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:approximation algorithm; budgeted maximum coverage; dynamic programming
MSC-Klassifikation:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) [See also 68Q15]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Datum der Erstveröffentlichung:07.05.2002
Schriftenreihe (Bandnummer):ZIB-Report (02-24)
ZIB-Reportnummer:02-24
Verlagspublikation:Appeared in: Graph-Theoretic Concepts in Computer Science. 28th Intern. Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002; revised papers. L. Kucera (ed.) Springer 2002. LNCS 2573. Pp. 321-332
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.