Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Graph Modification Problems: A Modern Perspective Read chapter Read first chapter

2015 | OriginalPaper | Chapter

The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation

Authors : Yusupjan Habibulla, Jin-Hua Zhao, Hai-Jun Zhou

Published in: Frontiers in Algorithmics

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A minimum dominating set for a digraph (directed graph) is a smallest set of vertices such that each vertex either belongs to this set or has at least one parent vertex in this set. We solve this hard combinatorial optimization problem approximately by a local algorithm of generalized leaf removal and by a message-passing algorithm of belief propagation. These algorithms can construct near-optimal dominating sets or even exact minimum dominating sets for random digraphs and also for real-world digraph instances. We further develop a core percolation theory and a replica-symmetric spin glass theory for this problem. Our algorithmic and theoretical results may facilitate applications of dominating sets to various network problems involving directed interactions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Social Models and Algorithms for Optimization of Contact Immunity of Oral Polio Vaccine
next chapter A Linear Time Algorithm for Ordered Partition
Appendix
Available only for authorised users
Literature
1.
2.
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)MATH
3.
Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)MATH
4.
5.
Gutin, G., Jones, M., Yeo, A.: Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems. Theor. Comput. Sci. 412, 5744–5751 (2011)MATHMathSciNetCrossRef
6.
Takaguchi, T., Hasegawa, T., Yoshida, Y.: Suppressing epidemics on networks by exploiting observer nodes. Phys. Rev. E 90, 012807 (2014)CrossRef
7.
Wuchty, S.: Controllability in protein interaction networks. Proc. Natl. Acad. Sci. USA 111, 7156–7160 (2014)CrossRef
8.
Wang, H., Zheng, H., Browne, F., Wang, C.: Minimum dominating sets in cell cycle specific protein interaction networks. In: Proceedings of International Conference on Bioinformatics and Biomedicine (BIBM 2014), pp. 25–30. IEEE (2014)
9.
10.
Yang, Y., Wang, J., Motter, A.E.: Network observability transitions. Phys. Rev. Lett. 109, 258701 (2012)CrossRef
11.
12.
Molnár Jr., F., Sreenivasan, S., Szymanski, B.K., Korniss, K.: Minimum dominating sets in scale-free network ensembles. Sci. Rep. 3, 1736 (2013)CrossRef
13.
14.
Bauer, M., Golinelli, O.: Core percolation in random graphs: a critical phenomena analysis. Eur. Phys. J. B 24, 339–352 (2001)CrossRef
15.
Liu, Y.Y., Csóka, E., Zhou, H.J., Pósfai, M.: Core percolation on complex networks. Phys. Rev. Lett. 109, 205703 (2012)CrossRef
16.
Richardson, M., Agrawal, R., Domingos, P.: Trust management for the semantic web. In: Fensel, D., Sycara, K., Mylopoulos, J. (eds.) ISWC 2003. LNCS, vol. 2870, pp. 351–368. Springer, Heidelberg (2003) CrossRef
17.
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 1361–1370. ACM, New York (2010)
18.
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: Proceedings of the 19th International Conference on World Wide Web, pp. 641–650. ACM, New York (2010)
19.
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: densification and shrinking diameters. ACM Trans. Knowl. Disc. Data 1, 2 (2007)
20.
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 177–187. ACM, New York (2005)
21.
Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6, 29–123 (2009)MATHMathSciNetCrossRef
22.
Ripeanu, M., Foster, I., Iamnitchi, A.: Mapping the gnutella network: properties of large-scale peer-to-peer systems and implications for system design. IEEE Internet Comput. 6, 50–57 (2002)
23.
Mézard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, New York (2009) MATHCrossRef
24.
Kschischang, F.R., Frey, B.J., Loeliger, H.A.: Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47, 498–519 (2001)MATHMathSciNetCrossRef
25.
Xiao, J.Q., Zhou, H.J.: Partition function loop series for a general graphical model: free-energy corrections and message-passing equations. J. Phys. A: Math. Theor. 44, 425001 (2011)MathSciNetCrossRef
26.
Zhou, H.J., Wang, C.: Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results. J. Stat. Phys. 148, 513–547 (2012)MATHMathSciNetCrossRef
27.
Mézard, M., Parisi, G.: The bethe lattice spin glass revisited. Eur. Phys. J. B 20, 217–233 (2001)CrossRef
28.
Zhao, J.H., Zhou, H.J.: Statistical physics of hard combinatorial optimization: vertex cover problem. Chin. Phys. B 23, 078901 (2014)CrossRef
Metadata
Title
The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
Authors
Yusupjan Habibulla
Jin-Hua Zhao
Hai-Jun Zhou
Copyright Year
2015
Book
Frontiers in Algorithmics

Print ISBN: 978-3-319-19646-6

Electronic ISBN: 978-3-319-19647-3

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-19647-3_8

Premium Partner

    Image Credits