Top

Published in:

2020 | OriginalPaper | Chapter

Efficient Enumeration of Non-isomorphic Ptolemaic Graphs

Authors : Dat Hoang Tran, Ryuhei Uehara

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Recently, a general framework for enumerating every element in a graph class was given. The main feature of this framework was that it was designed to enumerate only non-isomorphic graphs in a graph class. Applying this framework to the classes of interval graphs and permutation graphs, we gave efficient enumeration algorithms for these graph classes such that each element in the class was output in polynomial time delay. In this paper, we investigate the class of Ptolemaic graphs that consists of graphs that satisfy Ptolemy inequality for the distance. From the viewpoint of graph classes, it is an intersection of the class of chordal graphs and the class of distance-hereditary graphs. To enumerate Ptolemaic graphs, we need more tricks for applying the general framework. We develop an efficient enumeration algorithm for non-isomorphic Ptolemaic graphs.

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 Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs

next chapter Faster Privacy-Preserving Computation of Edit Distance with Moves

http://www.jaist.ac.jp/~uehara/graphs.

We use two terms “node” and “vertex” to indicate an element in a graph. When we use “vertex,” it indicates a vertex in the original chordal graph G. On the other hand, when we use “node,” it indicates a node of the clique tree.

In this context, when we use terms “node” in a minimal CL-tree \(\overrightarrow{T}(\mathcal{G})\) and “vertex” in a family tree \(\hat{T}\) to distinguish with them.

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

Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)CrossRef

Harasawa, S., Uehara, R.: Efficient enumeration of connected proper interval graphs. IEICE Technical report COMP2018-44, IEICE, pp. 9–16, March 2019. (in Japanese)

Howorka, E.: A characterization of ptolemaic graphs. J. Graph Theory 5, 323–331 (1981)MathSciNetCrossRef

Ikeda, S., Uehara, R.: Implementation of enumeration algorithm for connected bipartite permutation graphs. IEICE Technical report COMP2018-45, IEICE, pp. 17–23, March 2019. (in Japanese)

Nakano, S., Uno, T.: Constant time generation of trees with specified diameter. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 33–45. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30559-0_3CrossRef

Korte, B., Vygen, J.: Combinatorial Optimization. AC, vol. 21. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-662-56039-6CrossRefMATH

Mikos, P.: Efficient enumeration of non-isomorphic interval graphs. arXiv:1906.04094, June 2019

Saitoh, T., Otachi, Y., Yamanaka, K., Uehara, R.: Random generation and enumeration of bipartite permutation graphs. J. Discrete Algorithms 10, 84–97 (2012). https://doi.org/10.1016/j.jda.2011.11.001MathSciNetCrossRefMATH

10.

Saitoh, T., Yamanaka, K., Kiyomi, M., Uehara, R.: Random generation and enumeration of proper interval graphs. IEICE Trans. Inf. Syst. E93(D(7)), 1816–1823 (2010)CrossRef

11.

Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society, Providence (2003)CrossRef

12.

Uehara, R., Toda, S., Nagoya, T.: Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs. Discrete Appl. Math. 145(3), 479–482 (2004)MathSciNetCrossRef

13.

Uehara, R.: The graph isomorphism problem on geometric graphs. Discrete Math. Theoret. Comput. Sci. 16(2), 87–96 (2014)MathSciNetMATH

14.

Uehara, R., Uno, Y.: Laminar structure of ptolemaic graphs with applications. Discrete Appl. Math. 157(7), 1533–1543 (2009)MathSciNetCrossRef

15.

Yamazaki, K., Saitoh, T., Kiyomi, M., Uehara, R.: Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs. Theoret. Comput. Sci. (2019, accepted). https://doi.org/10.1016/j.tcs.2019.04.017 MathSciNetCrossRef

Title: Efficient Enumeration of Non-isomorphic Ptolemaic Graphs
Authors: Dat Hoang Tran
Ryuhei Uehara
Publisher: Springer International Publishing
Book: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_25

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner