TY - GEN
T1 - The density maximization problem in graphs
AU - Kao, Mong Jen
AU - Katz, Bastian
AU - Krug, Marcus
AU - Lee, D. T.
AU - Rutter, Ignaz
AU - Wagner, Dorothea
N1 - Funding Information:
Supported by NSC-DFG Projects NSC98-2221-E-001-007-MY3 and WA 654/18.
PY - 2011
Y1 - 2011
N2 - We consider a framework for bi-objective network construction problems where one objective is to be maximized while the other is to be minimized. Given a host graph G = (V,E) with edge weights we ∈ ℤ and edge lengths ℓe ∈ ℕ for e ∈ E we define the density of a pattern subgraph H = (V′,E′) ⊆ G as the ρ(H) = ∑eεE′we/∑eεE′ ℓe ratio . We consider the problem of computing a maximum density pattern H with weight at least W and and length at most L in a host G. We consider this problem for different classes of hosts and patterns. We show that it is NP-hard even if the host has treewidth 2 and the pattern is a path. However, it can be solved in pseudo-polynomial linear time if the host has bounded treewidth and the pattern is a graph from a given minor-closed family of graphs. Finally, we present an FPTAS for a relaxation of the density maximization problem, in which we are allowed to violate the upper bound on the length at the cost of some penalty.
AB - We consider a framework for bi-objective network construction problems where one objective is to be maximized while the other is to be minimized. Given a host graph G = (V,E) with edge weights we ∈ ℤ and edge lengths ℓe ∈ ℕ for e ∈ E we define the density of a pattern subgraph H = (V′,E′) ⊆ G as the ρ(H) = ∑eεE′we/∑eεE′ ℓe ratio . We consider the problem of computing a maximum density pattern H with weight at least W and and length at most L in a host G. We consider this problem for different classes of hosts and patterns. We show that it is NP-hard even if the host has treewidth 2 and the pattern is a path. However, it can be solved in pseudo-polynomial linear time if the host has bounded treewidth and the pattern is a graph from a given minor-closed family of graphs. Finally, we present an FPTAS for a relaxation of the density maximization problem, in which we are allowed to violate the upper bound on the length at the cost of some penalty.
UR - http://www.scopus.com/inward/record.url?scp=80051960500&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22685-4_3
DO - 10.1007/978-3-642-22685-4_3
M3 - Conference contribution
AN - SCOPUS:80051960500
SN - 9783642226847
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 25
EP - 36
BT - Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings
T2 - 17th Annual International Computing and Combinatorics Conference, COCOON 2011
Y2 - 14 August 2011 through 16 August 2011
ER -