Article

The prize-collecting edge dominating set problem in trees

Author:

MFCS'10: Proceedings of the 35th international conference on Mathematical foundations of computer science

Pages 465 - 476

Published: 23 August 2010 Publication History

Abstract

In this paper, we consider the prize-collecting edge dominating set problem, which is a generalization of the edge dominating set problem. In the prize-collecting edge dominating set problem, we are not forced to dominate all edges, but we need to pay penalties for edges which are not dominated. It is known that this problem is NP-hard, and Parekh presented a 8/3-approximation algorithm. To the best of our knowledge, no polynomial-time solvable case is known for this problem. In this paper, we show that the prize-collecting edge dominating set problem in trees can be solved in polynomial time.

References

[1]

Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM Journal on Applied Mathematics 38(3), 364-372 (1980).

Crossref

Google Scholar

[2]

Gotthilf, Z., Lewenstein, M., Rainshmidt, E.: A (2 - c log n/n) approximation algorithm for the minimum maximal matching problem. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol. 5426, pp. 267-278. Springer, Heidelberg (2009).

Digital Library

Google Scholar

[3]

Mitchell, S., Hedetniemi, S.: Edge domination in trees. In: Proceedings of the Eighth Southern Conference on Combinatorics, Graph Theory, and Computing, pp. 489-509 (1977).

Google Scholar

[4]

Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Discrete Applied Mathematics 118(3), 199-207 (2002).

Digital Library

Google Scholar

[5]

Parekh, O.: Edge dominating and hypomatchable sets. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 287-291 (2002).

Digital Library

Google Scholar

[6]

Berger, A., Parekh, O.: Linear time algorithms for generalized edge dominating set problems. Algorithmica 50(2), 244-254 (2008).

Digital Library

Google Scholar

[7]

Archer, A., Bateni, M., Hajiaghayi, M.T., Karloff, H.J.: Improved approximation algorithms for prize-collecting steiner tree and TSP. In: Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 427-436 (2009).

Digital Library

Google Scholar

[8]

Hochbaum, D.S.: Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. European Journal of Operational Research 140(2), 291-321 (2002).

Crossref

Google Scholar

[9]

Parekh, O.: Approximation algorithms for partially covering with edges. Theoretical Computer Science 400(1-3), 159-168 (2008).

Digital Library

Google Scholar

[10]

Schrijver, A.: Theory of Linear and Integer Programming. J. Wiley & Sons, Chichester (1986).

Digital Library

Google Scholar

[11]

Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. Annals of Discrete Mathematics 1, 185-204 (1977).

Crossref

Google Scholar

[12]

Hoffman, A.J., Kruskal, J.B.: Integral boundary points of convex polyhedra. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems, pp. 223-246. Princeton University Press, Princeton (1956).

Google Scholar

[13]

Ghouila-Houri, A.: Caractérisation des matrices totalement unimodulaires. Comptes Redus Hebdomadaires des Séances de l'Académie des Sciences (Paris) 254, 1192-1194 (1962).

Google Scholar

Cited By

View all

Catalano DFiore DGennaro RVamvourellis K(2019)Algebraic (trapdoor) one-way functionsTheoretical Computer Science10.1016/j.tcs.2015.05.029592:C(143-165)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2015.05.029
Wang YWei JRen SShen Y(2016)Toward integrity assurance of outsourced computing - a game theoretic perspectiveFuture Generation Computer Systems10.1016/j.future.2015.08.01055:C(87-100)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.future.2015.08.010
Fukunaga T(2016)Covering problems in edge- and node-weighted graphsDiscrete Optimization10.1016/j.disopt.2016.03.00120:C(40-61)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.disopt.2016.03.001

The prize-collecting edge dominating set problem in trees
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
2. Theory of computation

Recommendations

Minimum-Cost b-Edge Dominating Sets on Trees

In this paper, we consider the minimum-cost b-edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of ...
Minimum-Cost -Edge Dominating Sets on Trees
Algorithms and Computation
Abstract
We consider the minimum-cost -edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of this open ...
Independent dominating set problem revisited

An independent dominating set of a graph G is a subset D of V such that every vertex not in D is adjacent to at least one vertex of D and no two vertices in D are adjacent. The independent dominating set (IDS) problem asks for an independent dominating ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MFCS'10: Proceedings of the 35th international conference on Mathematical foundations of computer science

August 2010

714 pages

ISBN:364215154X

Editors:
Petr Hliněný
Masaryk University, Falculty of Informatics, Brno, Czech Republic
,
Antonín Kučera
Masaryk University, Falculty of Informatics, Brno, Czech Republic

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 August 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Catalano DFiore DGennaro RVamvourellis K(2019)Algebraic (trapdoor) one-way functionsTheoretical Computer Science10.1016/j.tcs.2015.05.029592:C(143-165)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2015.05.029
Wang YWei JRen SShen Y(2016)Toward integrity assurance of outsourced computing - a game theoretic perspectiveFuture Generation Computer Systems10.1016/j.future.2015.08.01055:C(87-100)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.future.2015.08.010
Fukunaga T(2016)Covering problems in edge- and node-weighted graphsDiscrete Optimization10.1016/j.disopt.2016.03.00120:C(40-61)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.disopt.2016.03.001

Abstract

References

Cited By

Recommendations

Minimum-Cost b-Edge Dominating Sets on Trees

Minimum-Cost -Edge Dominating Sets on Trees

Independent dominating set problem revisited

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations