View in EDS

DETECTING AND COUNTING SMALL PATTERN GRAPHS.

Saved in:
Bibliographic Details
Title: DETECTING AND COUNTING SMALL PATTERN GRAPHS.
Authors: FLODERUS, PETER1 Peter.Floderus@math.lu.se, KOWALUK, MIROSŁAW2 kowaluk@mimuw.edu.pl, LINGAS, ANDRZEJ3 Andrzej.Lingas@cs.lth.se, LUNDELL, EVA-MARTA3 Eva-Marta.Lundell@cs.lth.se
Source: SIAM Journal on Discrete Mathematics. 2015, Vol. 29 Issue 3, p1322-1339. 18p.
Subjects: Subgraphs, Isomorphism (Mathematics), Graph theory, Geometric vertices, Polynomials, Algorithms
Abstract: We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 117029357
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: DETECTING AND COUNTING SMALL PATTERN GRAPHS.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22FLODERUS%2C+PETER%22">FLODERUS, PETER</searchLink><relatesTo>1</relatesTo><i> Peter.Floderus@math.lu.se</i><br /><searchLink fieldCode="AR" term="%22KOWALUK%2C+MIROSŁAW%22">KOWALUK, MIROSŁAW</searchLink><relatesTo>2</relatesTo><i> kowaluk@mimuw.edu.pl</i><br /><searchLink fieldCode="AR" term="%22LINGAS%2C+ANDRZEJ%22">LINGAS, ANDRZEJ</searchLink><relatesTo>3</relatesTo><i> Andrzej.Lingas@cs.lth.se</i><br /><searchLink fieldCode="AR" term="%22LUNDELL%2C+EVA-MARTA%22">LUNDELL, EVA-MARTA</searchLink><relatesTo>3</relatesTo><i> Eva-Marta.Lundell@cs.lth.se</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Discrete+Mathematics%22">SIAM Journal on Discrete Mathematics</searchLink>. 2015, Vol. 29 Issue 3, p1322-1339. 18p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Subgraphs%22">Subgraphs</searchLink><br /><searchLink fieldCode="DE" term="%22Isomorphism+%28Mathematics%29%22">Isomorphism (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Geometric+vertices%22">Geometric vertices</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=117029357
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/140978211
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 18
        StartPage: 1322
    Subjects:
      – SubjectFull: Subgraphs
        Type: general
      – SubjectFull: Isomorphism (Mathematics)
        Type: general
      – SubjectFull: Graph theory
        Type: general
      – SubjectFull: Geometric vertices
        Type: general
      – SubjectFull: Polynomials
        Type: general
      – SubjectFull: Algorithms
        Type: general
    Titles:
      – TitleFull: DETECTING AND COUNTING SMALL PATTERN GRAPHS.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: FLODERUS, PETER
      – PersonEntity:
          Name:
            NameFull: KOWALUK, MIROSŁAW
      – PersonEntity:
          Name:
            NameFull: LINGAS, ANDRZEJ
      – PersonEntity:
          Name:
            NameFull: LUNDELL, EVA-MARTA
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 07
              Text: 2015
              Type: published
              Y: 2015
          Identifiers:
            – Type: issn-print
              Value: 08954801
          Numbering:
            – Type: volume
              Value: 29
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: SIAM Journal on Discrete Mathematics
              Type: main
ResultId 1