k-edge subgraph problems
| Autor: | Dorit S. Hochbaum, Olivier Goldschmidt |
|---|---|
| Rok vydání: | 1997 |
| Předmět: |
Combinatorics
Spanning tree Applied Mathematics Subgraph isomorphism problem Vertex cover Discrete Mathematics and Combinatorics Induced subgraph isomorphism problem Graph factorization Time complexity Maximum common subgraph isomorphism problem Mathematics Minimum degree spanning tree MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Discrete Applied Mathematics. 74(2):159-169 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/s0166-218x(96)00030-3 |
| Popis: | We study here a problem on graphs that involves finding a subgraph of maximum node weights spanning up to k edges. We interpret the concept of “spanning” to mean that at least one endpoint of the edge is in the subgraph in which we seek to maximize the total weight of the nodes. We discuss the complexity of this problem and other related problems with different concepts of “spanning” and show that most of these variants are NP-complete. For the problem defined, we demonstrate a factor 3 approximation algorithm with complexity O( kn ) for a graph on n nodes. For the unweighted version of the the problem in a graph on m edges we describe a factor 2 approximation algorithm of greedy type, with complexity O( n + m ). For trees and forests we present a polynomial time algorithm applicable to our problem and also to a problem seeking to maximize (minimize) the weight of a subtree on k nodes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect