nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Enumerating Connected Induced Subgraphs: Improved Delay and Experimental Comparison

verfasst von : Christian Komusiewicz, Frank Sommer

Erschienen in: SOFSEM 2019: Theory and Practice of Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider the problem of enumerating all connected induced subgraphs of order k in an undirected graph \(G=(V,E)\). Our main results are two enumeration algorithms with a delay of \(\mathcal {O}(k^2\varDelta )\) where \(\varDelta \) is the maximum degree in the input graph. This improves upon a previous delay bound [Elbassioni, JGAA 2015] for this problem. In addition, we give improved worst-case running time bounds and delay bounds for several known algorithms and perform an experimental comparison of these algorithms for \(k\le 10\) and \(k\ge |V|-3\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel On Point Set Embeddings for k-Planar Graphs with Few Bends per Edge

Nächstes Kapitel Multi-stranded String Assembling Systems

The source code of our program Enucon is available at www.uni-marburg.de/fb12/arbeitsgruppen/algorithmik/software/.

Avis, D., Fukuda, K.: Reverse search for enumeration. Discret. Appl. Math. 65(1–3), 21–46 (1996)MathSciNetCrossRef

Bader, D.A., Meyerhenke, H., Sanders, P., Schulz, C., Kappes, A., Wagner, D.: Benchmarking for graph clustering and partitioning. In: Alhajj, R., Rokne, J. (eds.) Encyclopedia of Social Network Analysis and Mining, pp. 73–82. Springer, New York (2014). https://doi.org/10.1007/978-1-4614-6170-8_23CrossRef

Bollobás, B.: The Art of Mathematics - Coffee Time in Memphis. Cambridge University Press, Cambridge (2006)CrossRef

Elbassioni, K.M.: A polynomial delay algorithm for generating connected induced subgraphs of a given cardinality. J. Graph Algorithms Appl. 19(1), 273–280 (2015)MathSciNetCrossRef

Elbassuoni, S., Blanco, R.: Keyword search over RDF graphs. In: Proceedings of the 20th ACM Conference on Information and Knowledge Management, (CIKM 2011), pp. 237–242. ACM (2011)

Kashani, Z.R.M., et al.: Kavosh: a new algorithm for finding network motifs. BMC Bioinform. 10, 318 (2009)CrossRef

Komusiewicz, C., Sorge, M.: Finding dense subgraphs of sparse graphs. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 242–251. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33293-7_23CrossRef

Komusiewicz, C., Sorge, M.: An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems. Discret. Appl. Math. 193, 145–161 (2015)MathSciNetCrossRef

Komusiewicz, C., Sorge, M., Stahl, K.: Finding connected subgraphs of fixed minimum density: implementation and experiments. In: Bampis, E. (ed.) SEA 2015. LNCS, vol. 9125, pp. 82–93. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20086-6_7CrossRef

10.

Kunegis, J.: KONECT: the Koblenz network collection. In: Proceedings of the 22nd International World Wide Web Conference (WWW 2013), pp. 1343–1350. International World Wide Web Conferences Steering Committee/ACM (2013)

11.

Maxwell, S., Chance, M.R., Koyutürk, M.: Efficiently enumerating all connected induced subgraphs of a large molecular network. In: Dediu, A.-H., Martín-Vide, C., Truthe, B. (eds.) AlCoB 2014. LNCS, vol. 8542, pp. 171–182. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07953-0_14CrossRef

12.

Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), pp. 4292–4293. AAAI Press (2015). http://networkrepository.com

13.

Wernicke, S.: A faster algorithm for detecting network motifs. In: Casadio, R., Myers, G. (eds.) WABI 2005. LNCS, vol. 3692, pp. 165–177. Springer, Heidelberg (2005). https://doi.org/10.1007/11557067_14CrossRef

14.

Wernicke, S.: Combinatorial algorithms to cope with the complexity of biological networks. Ph.D. thesis, Friedrich Schiller University of Jena (2006). http://d-nb.info/982598882

Titel: Enumerating Connected Induced Subgraphs: Improved Delay and Experimental Comparison
verfasst von: Christian Komusiewicz
Frank Sommer
Verlag: Springer International Publishing
Buch: SOFSEM 2019: Theory and Practice of Computer Science
Print ISBN: 978-3-030-10800-7

Electronic ISBN: 978-3-030-10801-4

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-10801-4_22

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"