Efficient Enumeration of Non-isomorphic Ptolemaic Graphs
| Autor: | Dat Hoang Tran, Ryuhei Uehara |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematics::Combinatorics
Computer science Enumeration algorithm 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics Chordal graph 0202 electrical engineering electronic engineering information engineering Enumeration 020201 artificial intelligence & image processing Time complexity MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | WALCOM: Algorithms and Computation ISBN: 9783030398804 WALCOM |
| DOI: | 10.1007/978-3-030-39881-1_25 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|