Name
Title | ||
|---|---|---|
Implicit Enumeration Of Topological-Minor-Embeddings And Its Application To Planar Subgraph Enumeration |
Abstract | ||
|---|---|---|
Given graphs G and H, we propose a method to implicitly enumerate topological-minor-embeddings of H in G using decision diagrams. We show a useful application of our method to enumerating subgraphs characterized by forbidden topological minors, that is, planar, outerplanar, series-parallel, and cactus subgraphs. Computational experiments show that our method can find all planar subgraphs in a given graph at most five orders of magnitude faster than a naive backtracking-based method. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-39881-1_18 | WALCOM: ALGORITHMS AND COMPUTATION (WALCOM 2020) |
Keywords | Field | DocType |
Graph algorithm, Enumeration problem, Decision diagram, Frontier-based search, Topological minor | Topology,Discrete mathematics,Graph,Graph algorithms,Combinatorics,Computer science,Enumeration,Influence diagram,Planar,Backtracking | Conference |
Volume | ISSN | Citations |
12049 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yu Nakahata | 1 | 0 | 2.03 |
| Jun Kawahara | 2 | 34 | 8.82 |
| Takashi Horiyama | 3 | 81 | 19.76 |
| Shin-ichi Minato | 4 | 725 | 84.72 |