Open Access
Issue
RAIRO-Oper. Res.
Volume 53, Number 5, November-December 2019
Page(s) 1763 - 1773
DOI https://doi.org/10.1051/ro/2018076
Published online 09 October 2019
  • A. Agra, D. Cardoso, O. Cerfeira and E. Rocha, A spanning star forest model for the diversity problem in automobile industry. In: ECCO XVIII, Minsk (2005). [Google Scholar]
  • S. Athanassopoulos, I. Caragiannis, C. Kaklamanis and M. Kyropoulou, An improved approximation bound for spanning star forest and color saving. In: MFCS. Springer, Berlin, Heidelberg (2009) 90–101. [Google Scholar]
  • M. Baïou and F. Barahona, On the integrality of some facility location polytopes. SIAM J. Discrete Math. 23 (2009) 665–679. [Google Scholar]
  • M. Baïou, F. Barahona, Simple extended formulation for the dominating set polytope via facility location, Tech. Rep. RC25325, IBM Research (2012). [Google Scholar]
  • M. Baïou, F. Barahona, Algorithms for minimum weighted dominating sets in cycles and cacti, Tech. Rep. RC25488, IBM Research (2014). [Google Scholar]
  • M. Baïou and F. Barahona, The dominating set polytope via facility location. Combinatorial Optimization. ISCO 2014. In Vol. 8596 of Lecture Note Computer Sciences (2014) 38–49. [Google Scholar]
  • V. Berry, S. Guillemot, F. Nicholas and C. Paul, On the approximation of computing evolutionary trees. In: Proc. of the Eleventh Annual International Computing and Combinatorics Conference. Springer, Berlin, Heidelberg (2005) 115–123. [Google Scholar]
  • M. Bouchakour, T.M. Contenza, C.W. Lee and A.R. Mahjoub, On the dominating set polytope. Eur. J. Combin. 29 (2008) 652–661. [Google Scholar]
  • M. Bouchakour and A.R. Mahjoub, One-node cutsets and the dominating set polytope. Discrete Math. 165/166 (1997) 101–123. [Google Scholar]
  • B.-M. Bui-Xuan, J.A. Telle and M. Vatshelle, Boolean-width of graphs. Theoret. Comput. Sci. 412 (2011) 5187–5204. [Google Scholar]
  • D. Chakrabarty and G. Goel, On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. In: FOCS ‘08. IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, 1975 (2008) 687–696. [Google Scholar]
  • N. Chen, R. Engelberg, C.T. Nguyen, P. Raghavendra, A. Rudra and G. Singh, Improved approximation algorithms for the spanning star forest problem. In: APPROX/RANDOM In Vol. 4627 of Lecture Notes in Computer Science book series (2007) 44–58. [Google Scholar]
  • T.W. Haynes, P.J. Slater and S.T. Hedetniemi, Fundamentals of Domination in Graphs. CRC Press, Boca Raton, FL (1998). [Google Scholar]
  • J. He and H. Liang, On variants of the spanning star forest problem. In: Proc. of FAW-AAIM (2011) 70–81. [Google Scholar]
  • T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi and Y. Okamoto, Minimum-cost b -edge dominating sets on trees. In, Vol. 8880 of Lecture Notes Computer Sciences (2014) 195–207. [Google Scholar]
  • A.R. Mahjoub, Polytope des absorbants dans une classe de graphes seuil. Annal. Discrete Math. 17 (1983) 443–452. [Google Scholar]
  • C.T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller and L. Zhang, Approximating the spanning star forest problem and its applications to genomic sequence alignment. In: Proc. of SODA (2007) 645–654. [Google Scholar]
  • V.H. Nguyen, The maximum weight spanning star forest problem on cactus graphs. Discrete Math. Algorithms App. 7 (2015) 1550018. [Google Scholar]
  • A. Saxena, Some results on the dominating set polytope of a cycle. Technical Report CMU (2004). [Google Scholar]
  • M. Yannakakis and F. Gavril, Edge dominating sets in graphs. SIAM J. Appl Math. 38 (1980) 364–372. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.