Isomorphic subgraphs (Q4501707)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1500686
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Isomorphic subgraphs |
scientific article; zbMATH DE number 1500686 |
Statements
15 July 2001
0 references
subgraph isomorphism
0 references
NP-completeness
0 references
graph drawing
0 references
graph summetry
0 references
0.8456383943557739
0 references
0.7776252627372742
0 references
0.7743728756904602
0 references
0.7572730779647827
0 references
Isomorphic subgraphs (English)
0 references
New isomorphic subgraph problems IES (edge-induced) and INS (node-induced) are investigated and their NP-completeness is proved for the general case and for numerous special cases of graphs. The investigated problems are seen as the general tools for demonstrating a symmetry of a graph. Finding two maximal edge-induced or node-induced graphs seems to be really the general criterion for demonstrating an internal structure of a graph. Therefore, the author claims that splitting a graph for two maximal isomorphic subgraphs and a remineder can be used as a foundation for graph drawing, he is going to develop layout for graph visualization using the isomorphic subgraph approach. There is also given a short survey of graph isomorphism and related problems. However, treating CLIQUE or HAMILTIONIAN as special cases of subgraph isomorphism seems to be arbitrary and usable only for very restricted claims. For the entire collection see [Zbl 0931.00046].
0 references
