All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F19%3A00339008" target="_blank" >RIV/68407700:21240/19:00339008 - isvavai.cz</a>

  • Result on the web

    <a href="https://doi.org/10.1007/978-3-030-34029-2_19" target="_blank" >https://doi.org/10.1007/978-3-030-34029-2_19</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1007/978-3-030-34029-2_19" target="_blank" >10.1007/978-3-030-34029-2_19</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem

  • Original language description

    We consider the subgraph isomorphism problem where, given two graphs G (source graph) and F (pattern graph), one is to decide whether there is a (not necessarily induced) subgraph of G isomorphic to F. While many practical heuristic algorithms have been developed for the problem, as pointed out by McCreesh et al. [JAIR 2018], for each of them there are rather small instances which they cannot cope. Therefore, developing an alternative approach that could possibly cope with these hard instances would be of interest. A seminal paper by Alon, Yuster and Zwick [J. ACM 1995] introduced the color coding approach to solve the problem, where the main part is a dynamic programming over color subsets and partial mappings. As with many exponential-time dynamic programming algorithms, the memory requirements constitute the main limiting factor for its usage. Because these requirements grow exponentially with the treewidth of the pattern graph, all existing implementations based on the color coding principle restrict themselves to specific pattern graphs, e.g., paths or trees. In contrast, we provide an efficient implementation of the algorithm significantly reducing its memory requirements so that it can be used for pattern graphs of larger treewidth. Moreover, our implementation not only decides the existence of an isomorphic subgraph, but it also enumerates all such subgraphs (or given number of them). We provide an extensive experimental comparison of our implementation to other available solvers for the problem.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • Project

    Result was created during the realization of more than one project. More information in the Projects tab.

  • Continuities

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Others

  • Publication year

    2019

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Article name in the collection

    Analysis of Experimental Algorithms

  • ISBN

    978-3-030-34028-5

  • ISSN

    0302-9743

  • e-ISSN

    1611-3349

  • Number of pages

    17

  • Pages from-to

    283-299

  • Publisher name

    Springer Nature Switzerland AG

  • Place of publication

    Basel

  • Event location

    Kalamata

  • Event date

    Jun 24, 2019

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article