Name
Abstract | ||
|---|---|---|
Given an edge weighted undirected graph (G=(V,E)) with (|V|=n), and a function (f:Vrightarrow mathbb {N}), we consider the problem of finding a connected f-factor in G. In particular, for each constant (c ge 2), we consider the case when (f(v)ge frac{n}{c}), for all v in V. We characterize the set of graphs that have a connected f-factor for (f(v) ge frac{n}{3}), for every v in V, and this gives polynomial time algorithm for the decision version of the problem. Extending the techniques we solve the minimization version. On the class of instances where the edge weights in G form a metric and (f(v) ge frac{n}{c}), c is a fixed value greater than 3, we give a PTAS. For each (c ge 3) and (epsilon u003e 0), our algorithm takes as input a metric weighted undirected graph G and a function (f:Vrightarrow mathbb {N}) such that (f(v) ge frac{n}{c}), for every v in V, and computes a ((1+epsilon ))-approximation to the minimum weighted connected f-factor in polynomial time. |
Year | Venue | Field |
|---|---|---|
2015 | CSR | Graph,Discrete mathematics,Approximation algorithm,Combinatorics,Computer science,Algorithm,Time complexity |
DocType | Citations | PageRank |
Conference | 2 | 0.40 |
References | Authors | |
4 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| N. S. Narayanaswamy | 1 | 151 | 27.01 |
| C. S. Rahul | 2 | 2 | 2.43 |