Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Efficient Local Search for Minimum Dominating Sets in Large Graphs

  • Conference paper
  • First Online:

Abstract

The Minimum Dominating Set (MinDS) problem is an NP-hard problem of great importance in both theories and applications. In this paper, we propose a new local search algorithm ScBppw (Score Checking and Best-picking with Probabilistic Walk) to solve the MinDS problem in large graphs. For diversifying the search, our algorithm exploits a tabu strategy, called Score Checking (SC), which forbids a vertex to be added into the current candidate solution if the vertex’s score has not been changed since the last time it was removed out of the candidate solution. Also, to keep a good balance between intensification and diversification during the search, we propose a strategy that combines, in a novel way, best-picking with probabilistic walk at removing stages. At this stage, the algorithm selects a vertex with the minimum loss, or other vertices in the candidate solution with a probability proportional to the their degrees, depending on how repeatedly the area has been visited. Experimental results show that our solver significantly outperforms state-of-the-art MinDS solvers. Also we conducted several experiments to show the individual impacts of our novelties.

Supported by the Natural Science Foundation of China (61672441, 61872154), the Shenzhen Basic Research Program (JCYJ20170818141325209), and the NSF grants (IIS-1814745, IIS-1302164).

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11210
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14013
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Notes

  1. 1.
  2. 2.

    In some graphs there are vertices whose degree is 0. In these cases, we prevent such vertices from being removed.

References

  1. Abseher, M., Dusberger, F., Musliu, N., Woltran, S.: Improving the efficiency of dynamic programming on tree decompositions via machine learning. In: IJCAI 2015, pp. 275–282 (2015)

    Google Scholar 

  2. Alber, J., Fellows, M.R., Niedermeier, R.: Efficient data reduction forDominating Set: a linear problem kernel for the planar case. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 150–159. Springer, Heidelberg (2002).https://doi.org/10.1007/3-540-45471-3_16

    Chapter  Google Scholar 

  3. Barabasi, A.L., Albert, R.: Emergence of scaling in random networks. Science286(5439), 509–512 (1999)

    Article MathSciNet  Google Scholar 

  4. Cai, S., Su, K., Luo, C., Sattar, A.: NuMVC: an efficient local search algorithm for minimum vertex cover. J. Artif. Intell. Res. (JAIR)46, 687–716 (2013)

    Article MathSciNet  Google Scholar 

  5. Cai, S., Su, K., Sattar, A.: Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artif. Intell.175(9–10), 1672–1696 (2011)

    Article MathSciNet  Google Scholar 

  6. Campan, A., Truta, T.M., Beckerich, M.: Fast dominating set algorithms for social networks. In: Proceedings of the 26th Modern AI and Cognitive Science Conference 2015, pp. 55–62 (2015)

    Google Scholar 

  7. Chalupa, D.: An order-based algorithm for minimum dominating set with application in graph mining. Inf. Sci.426, 101–116 (2018)

    Article MathSciNet  Google Scholar 

  8. Chung, F.R., Lu, L.: Complex graphs and networks, vol. 107 (2006)

    Google Scholar 

  9. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)

    MATH  Google Scholar 

  10. Eubank, S., Kumar, V.S.A., Marathe, M.V., Srinivasan, A., Wang, N.: Structural and algorithmic aspects of massive social networks. In: Proceedings of SODA 2004, pp. 718–727 (2004)

    Google Scholar 

  11. Fan, Y., Li, C., Ma, Z., Wen, L., Sattar, A., Su, K.: Local search for maximum vertex weight clique on large sparse graphs with efficient data structures. In: Kang, B.H., Bai, Q. (eds.) AI 2016. LNCS (LNAI), vol. 9992, pp. 255–267. Springer, Cham (2016).https://doi.org/10.1007/978-3-319-50127-7_21

    Chapter  Google Scholar 

  12. Fan, Y., Li, N., Li, C., Ma, Z., Latecki, L.J., Su, K.: Restart and random walk in local search for maximum vertex weight cliques with evaluations in clustering aggregation. In: IJCAI 2017, Melbourne, Australia, 19–25 August 2017, pp. 622–630 (2017)

    Google Scholar 

  13. Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Discrete Math.15(4), 519–529 (2002)

    Article MathSciNet  Google Scholar 

  14. Hedar, A.R., Ismail, R.: Simulated annealing with stochastic local search for minimum dominating set problem. Int. J. Mach. Learn. Cybern.3(2), 97–109 (2012)

    Article  Google Scholar 

  15. Hoos, H.H., Stützle, T.: Stochastic local search. In: Handbook of Approximation Algorithms and Metaheuristics (2007)

    Google Scholar 

  16. Jiang, H., Li, C., Manyà, F.: An exact algorithm for the maximum weight clique problem in large graphs. In: AAAI, California, USA, pp. 830–838 (2017)

    Google Scholar 

  17. Li, C.M., Huang, W.Q.: Diversification and determinism in local search for satisfiability. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 158–172. Springer, Heidelberg (2005).https://doi.org/10.1007/11499107_12

    Chapter  Google Scholar 

  18. Ma, Z., Fan, Y., Su, K., Li, C., Sattar, A.: Local search with noisy strategy for minimum vertex cover in massive graphs. In: Booth, R., Zhang, M.-L. (eds.) PRICAI 2016. LNCS (LNAI), vol. 9810, pp. 283–294. Springer, Cham (2016).https://doi.org/10.1007/978-3-319-42911-3_24

    Chapter  Google Scholar 

  19. Murray, R.S.: Theory and Problems of Probability and Statistics. McGraws-Hill Book and Co., Singapore (1975)

    Google Scholar 

  20. Nacher, J.C., Akutsu, T.: Minimum dominating set-based methods for analyzing biological networks. Methods102, 57–63 (2016)

    Article  Google Scholar 

  21. Potluri, A., Bhagvati, C.: Novel morphological algorithms for dominating sets on graphs with applications to image analysis. In: Barneva, R.P., Brimkov, V.E., Aggarwal, J.K. (eds.) IWCIA 2012. LNCS, vol. 7655, pp. 249–262. Springer, Heidelberg (2012).https://doi.org/10.1007/978-3-642-34732-0_19

    Chapter MATH  Google Scholar 

  22. Samuel, H., Zhuang, W., Preiss, B.: DTN based dominating set routing for manet in heterogeneous wireless networking. Mob. Netw. Appl.14(2), 154–164 (2009)

    Article  Google Scholar 

  23. Shen, C., Li, T.: Multi-document summarization via the minimum dominating set. In: COLING 2010, Beijing, China, pp. 984–992 (2010)

    Google Scholar 

  24. Wang, Y., Cai, S., Chen, J., Yin, M.: A fast local search algorithm for minimum weight dominating set problem on massive graphs. In: IJCAI 2018, pp. 1514–1522 (2018)

    Google Scholar 

  25. Wang, Y., Cai, S., Yin, M.: Local search for minimum weight dominating set with two-level configuration checking and frequency based scoring function. J. Artif. Intell. Res.58, 267–295 (2017)

    Article MathSciNet  Google Scholar 

  26. Yao, B., Fei-Fei, L.: Action recognition with exemplar based 2.5D graph matching. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds.) ECCV 2012. LNCS, vol. 7575, pp. 173–186. Springer, Heidelberg (2012).https://doi.org/10.1007/978-3-642-33765-9_13

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Shenzhen Research Institute/Software School, Xiamen University, Xiamen, China

    Yi Fan & Yongxuan Lai

  2. Guangxi Key Lab of Trusted Software, Guilin University of Electronic Technology, Guilin, China

    Yi Fan

  3. Griffith University, Brisbane, Australia

    Yi Fan, Zongjie Ma, Jun Zhou & Kaile Su

  4. NetEase Guangzhou AI Lab, Guangzhou, China

    Chengqian Li

  5. Temple University, Philadelphia, USA

    Nan Li & Longin Jan Latecki

Authors
  1. Yi Fan

    You can also search for this author inPubMed Google Scholar

  2. Yongxuan Lai

    You can also search for this author inPubMed Google Scholar

  3. Chengqian Li

    You can also search for this author inPubMed Google Scholar

  4. Nan Li

    You can also search for this author inPubMed Google Scholar

  5. Zongjie Ma

    You can also search for this author inPubMed Google Scholar

  6. Jun Zhou

    You can also search for this author inPubMed Google Scholar

  7. Longin Jan Latecki

    You can also search for this author inPubMed Google Scholar

  8. Kaile Su

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toYongxuan Lai.

Editor information

Editors and Affiliations

  1. Tsinghua University, Beijing, China

    Guoliang Li

  2. Duke University, Durham, NC, USA

    Jun Yang

  3. University of Porto, Porto, Portugal

    Joao Gama

  4. Chiang Mai University, Chiang Mai, Thailand

    Juggapong Natwichai

  5. Beihang University, Beijing, China

    Yongxin Tong

Rights and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Fan, Y.et al. (2019). Efficient Local Search for Minimum Dominating Sets in Large Graphs. In: Li, G., Yang, J., Gama, J., Natwichai, J., Tong, Y. (eds) Database Systems for Advanced Applications. DASFAA 2019. Lecture Notes in Computer Science(), vol 11447. Springer, Cham. https://doi.org/10.1007/978-3-030-18579-4_13

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11210
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14013
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp