|
Scheda bibliografica proveniente da importazione di metadati da altro sistema |
| Tipo: |
Testo a stampa, Risorsa analitica |
| É contributo di: |
Graph-based representations in pattern recognition ; pp. 71-80 |
| Titolo: |
A Bound for Non-subgraph Isomorphism |
| Pubblicazione: |
Berlin ; Heidelberg ; New York : Springer, ©2007 |
| Titolo uniforme: |
Graph-based representations in pattern recognition |
| Numeri standard: |
DOI 10.1007/978-3-540-72903-7_7  |
| Sommario o abstract: |
In this paper we propose a new lower bound to a subgraph isomorphism problem. This bound can provide a proof that no subgraph isomorphism between two graphs can be found. The computation is based on the SDP relaxation of a GÇô to the best of our knowledge GÇô new combinatorial optimisation formulation for subgraph isomorphism. We consider problem instances where only the structures of the two graph instances are given and therefore we deal with simple graphs in the first place. The idea is based on the fact that a subgraph isomorphism for such problem instances always leads to 0 as lowest possible optimal objective value for our combinatorial optimisation problem formulation. Therefore, a lower bound that is larger than 0 represents a proof that a subgraph isomorphism donGÇÖt exist in the problem instance. But note that conversely, a negative lower bound does not imply that a subgraph isomorphism must be present and only indicates that a subgraph isomorphism is still possible |
| Altra responsabilità: |
Christian Schellewald |
| Classificazione Dewey: |
006 ed.22 Metodi speciali di elaborazione |
| Lingua della pubblicazione: |
Inglese |
| Paese di pubblicazione: |
Germania ; Stati Uniti d'America |
| Codice identificativo: |
IT/ItRC/00017347 |
| data di importazione: |
01-01-2014 |
|
Full text |
Lista sintetica
CNR - Area della Ricerca di Genova Servizio di Documentazione Scientifica
SEI QUI: HOME
SCHEDA BIBLIOGRAFICA
