<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>691</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-05-07</completedDate>
    <publishedDate>2002-05-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Budgeted Maximal Graph Coverage</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">02-24</identifier>
    <identifier type="opus3-id">692</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6918</identifier>
    <enrichment key="SourceTitle">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</enrichment>
    <author>Sven Krumke</author>
    <author>Madhav Marathe</author>
    <author>Diana Poensgen</author>
    <author>Sekharipuram S. Ravi</author>
    <author>Hans-Christoph Wirth</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-24</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>budgeted maximum coverage</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>approximation algorithm</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>dynamic programming</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68Q17">Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) [See also 68Q15]</collection>
    <collection role="msc" number="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/691/ZR-02-24.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/691/ZR-02-24.pdf</file>
  </doc>
</export-example>
