Name
Abstract | ||
|---|---|---|
In the context of the chromatic-number problem, a critical graph is an instance where the deletion of any element would decrease the graphu0027s chromatic number. Such instances have shown to be interesting objects of study for deepen the understanding of the optimization problem. This work introduces critical graphs in context of Minimum Vertex Cover. We demonstrate their potential for the generation of larger graphs with hidden a priori known solutions. Firstly, we propose a parametrized graph-generation process which preserves the knowledge of the minimum cover. Secondly, we conduct a systematic search for small critical graphs. Thirdly, we illustrate the applicability for benchmarking purposes by reporting on a series of experiments using the state-of-the-art heuristic solver NuMVC. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Discrete Mathematics | Discrete mathematics,Indifference graph,Edge cover,Vertex (graph theory),Chordal graph,Vertex cover,Feedback vertex set,Mathematics,Maximal independent set,Bidimensionality |
DocType | Volume | Citations |
Journal | abs/1705.04111 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Jakoby | 1 | 141 | 17.68 |
| Naveen Kumar Goswami | 2 | 0 | 0.34 |
| Eik List | 3 | 111 | 13.70 |
| Stefan Lucks | 4 | 1083 | 108.87 |