Mishra, Sounaka ; Raman, Venkatesh ; Saurabh, Saket ; Sikdar, Somnath ; Subramanian, C. R. (2011) The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover Algorithmica, 61 (4). pp. 857-881. ISSN 0178-4617
Full text not available from this repository.
Official URL: http://doi.org/10.1007/s00453-010-9412-2
Related URL: http://dx.doi.org/10.1007/s00453-010-9412-2
Abstract
A graph is König-Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been studied extensively from a graph-theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding König-Egerváry subgraphs of a given graph. In particular, given a graph G and a nonnegative integer k, we are interested in the following questions: 1. does there exist a set of k vertices (edges) whose deletion makes the graph König-Egerváry? 2. does there exist a set of k vertices (edges) that induce a König-Egerváry subgraph?
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag. |
| ID Code: | 123460 |
| Deposited On: | 20 Sep 2021 08:17 |
| Last Modified: | 20 Sep 2021 08:17 |
Repository Staff Only: item control page
