Name
Abstract | ||
|---|---|---|
For a finite, simple, undirected graph G and an integer d ≥ 1, a mindeg-d subgraph is a subgraph of G of minimum degree at least d. The d-girth of G, denoted gd(G), is the minimum size of a mindeg-d subgraph of G. It is a natural generalization of the usual girth, which coincides with the 2-girth. The notion of d-girth was proposed by Erdös et al. [13, 14] and Bollob10:03 AM 2/4/2011aacute;s and Brightwell [7] over 20 years ago, and studied from a purely combinatorial point of view. Since then, no new insights have appeared in the literature. Recently, first algorithmic studies of the problem have been carried out [2,4]. The current article further explores the complexity of finding a small mindeg-d subgraph of a given graph (that is, approximating its d-girth), by providing new hardness results and the first approximation algorithms in general graphs, as well as analyzing the case where G is planar. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.dam.2013.04.022 | Discrete Applied Mathematics |
Keywords | Field | DocType |
general graph,mindeg-d subgraph,minimum size,undirected graph,approximation algorithm,algorithmic study,small mindeg-d subgraph,new hardness result,new insight,minimum degree,randomized algorithm,planar graph,hardness of approximation | Discrete mathematics,Combinatorics,Forbidden graph characterization,Graph power,Graph factorization,Induced subgraph isomorphism problem,Distance-hereditary graph,Factor-critical graph,Universal graph,Subgraph isomorphism problem,Mathematics | Conference |
Volume | Issue | ISSN |
161 | 16 | 0166-218X |
Citations | PageRank | References |
1 | 0.36 | 24 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Peleg | 1 | 6662 | 824.19 |
| Ignasi Sau | 2 | 243 | 37.18 |
| Mordechai Shalom | 3 | 162 | 24.67 |