nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs

verfasst von : Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, Ryo Yoshinaka

Erschienen in: Analysis of Experimental Algorithms

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

This paper considers enumeration of specific subgraphs of a given graph by using a data structure called a zero-suppressed binary decision diagram (ZDD). A ZDD can represent the set of solutions quite compactly. Recent studies have demonstrated that a technique generically called frontier-based search (FBS) is a powerful framework for using ZDDs to enumerate various yet rather simple types of subgraphs. We in this paper, propose colorful FBS, an enhancement of FBS, which enables us to enumerate more complex types of subgraphs than existing FBS techniques do. On the basis of colorful FBS, we design methods that construct ZDDs representing the sets of chordal and interval subgraphs from an input graph. Computer experiments show that the proposed methods run faster than reverse search based algorithms.

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 New Rebalancing Algorithm

Nächstes Kapitel Unit Disk Cover for Massive Point Sets

Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1–3), 21–46 (1996). https://doi.org/10.1016/0166-218X(95)00026-NMathSciNetCrossRefMATH

Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30(3), 479–513 (1983). https://doi.org/10.1145/2402.322389MathSciNetCrossRefMATH

Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation. The IMA Volumes in Mathematics and its Applications, vol. 56, pp. 1–29. Springer, New York, New York, NY (1993). https://doi.org/10.1007/978-1-4613-8369-7_1CrossRef

Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C–35(8), 677–691 (1986). https://doi.org/10.1109/TC.1986.1676819CrossRefMATH

Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol. 57). North-Holland Publishing Co., Amsterdam (2004)

Inoue, T., et al.: Distribution loss minimization with guaranteed error bound. IEEE Trans. Smart Grid 5(1), 102–111 (2014). https://doi.org/10.1109/TSG.2013.2288976CrossRef

Ishioka, F., Kawahara, J., Mizuta, M., Minato, S., Kurihara, K.: Evaluation of hotspot cluster detection using spatial scan statistic based on exact counting. Jpn. J. Stat. Data Sci. 2(1), 1–15 (2019). https://doi.org/10.1007/s42081-018-0030-6MathSciNetCrossRefMATH

Iwashita, H., Minato, S.: Efficient top-down ZDD construction techniques using recursive specifications. TCS Technical Reports TCS-TR-A-13-69 (2013)

Jackowski, Z.: A new characterization of proper interval graphs. Discrete Math. 105(1), 103–109 (1992). https://doi.org/10.1016/0012-365X(92)90135-3MathSciNetCrossRefMATH

10.

Kawahara, J., Horiyama, T., Hotta, K., Minato, S.: Generating all patterns of graph partitions within a disparity bound. In: Poon, S.-H., Rahman, M.S., Yen, H.-C. (eds.) WALCOM 2017. LNCS, vol. 10167, pp. 119–131. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53925-6_10CrossRef

11.

Kawahara, J., Inoue, T., Iwashita, H., Minato, S.: Frontier-based search for enumerating all constrained subgraphs with compressed representation. IEICE Trans. Inf. Syst. E100–A(9), 1773–1784 (2017)CrossRef

12.

Kawahara, J., Saitoh, T., Suzuki, H., Yoshinaka, R.: Solving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs. In: Phon-Amnuaisuk, S., Au, T.-W., Omar, S. (eds.) CIIS 2016. AISC, vol. 532, pp. 294–305. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-48517-1_26CrossRef

13.

Kiyomi, M., Kijima, S., Uno, T.: Listing chordal graphs and interval graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 68–77. Springer, Heidelberg (2006). https://doi.org/10.1007/11917496_7CrossRef

14.

Kiyomi, M., Uno, T.: Generating chordal graphs included in given graphs. IEICE Trans. Inf. Syst. E89–D(2), 763–770 (2006). https://doi.org/10.1093/ietisy/e89-d.2.763CrossRef

15.

Knight, S., Nguyen, H.X., Falkner, N., Bowden, R., Roughan, M.: The internet topology zoo. IEEE J. Sel. Areas Commun. 29(9), 1765–1775 (2011). https://doi.org/10.1109/JSAC.2011.111002CrossRef

16.

Knuth, D.E.: The Art of Computer Programming. Combinatorial Algorithms, Part 1, vol. 4A. Addison-Wesley, Upper Saddle River (2011)MATH

17.

Kunegis, J.: KONECT: the Koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 1343–1350 (2013). https://doi.org/10.1145/2487788.2488173

18.

Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae 51(1), 45–64 (1962)MathSciNetCrossRef

19.

Maehara, T., Suzuki, H., Ishihata, M.: Exact computation of influence spread by binary decision diagrams. In: Proceedings of the 26th International Conference on World Wide Web, pp. 947–956 (2017). https://doi.org/10.1145/3038912.3052567

20.

Miller, D.: Multiple-valued logic design tools. In: Proceedings of the 23rd International Symposium on Multiple-Valued Logic, pp. 2–11 (1993). https://doi.org/10.1109/ISMVL.1993.289589

21.

Minato, S.: Zero-suppressed BDDs for set manipulation in combinatorial problems. In: Proceedings of the 30th ACM/IEEE Design Automation Conference, pp. 272–277 (1993). https://doi.org/10.1145/157485.164890

22.

Pereira, F.M.Q., Palsberg, J.: Register allocation via coloring of chordal graphs. In: Yi, K. (ed.) APLAS 2005. LNCS, vol. 3780, pp. 315–329. Springer, Heidelberg (2005). https://doi.org/10.1007/11575467_21CrossRef

23.

de Ridder, H.N., et al.: Information System on Graph Classes and their Inclusions (ISGCI). http://www.graphclasses.org

24.

Sekine, K., Imai, H., Tani, S.: Computing the Tutte polynomial of a graph of moderate size. In: Staples, J., Eades, P., Katoh, N., Moffat, A. (eds.) ISAAC 1995. LNCS, vol. 1004, pp. 224–233. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0015427CrossRef

25.

Wasa, K.: Enumeration of enumeration algorithms. CoRR abs/1605.05102 (2016)

Titel: Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs
verfasst von: Jun Kawahara
Toshiki Saitoh
Hirofumi Suzuki
Ryo Yoshinaka
Verlag: Springer International Publishing
Buch: Analysis of Experimental Algorithms
Print ISBN: 978-3-030-34028-5

Electronic ISBN: 978-3-030-34029-2

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-34029-2_9

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"

Premium Partner