Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficient algorithms for subgraph listing
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Department of Computer Science, Lund University, Lund, Sweden.
2014 (English)In: Algorithms, E-ISSN 1999-4893, Vol. 7, no 2, p. 243-252Article in journal (Refereed) Published
Abstract [en]

Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to Chiba and Nishizeki for listing complete subgraphs of fixed size, and show that it cannot be extended to general subgraphs of fixed size. Then, we consider the algorithm due to Gąsieniec et al. for finding multiple witnesses of a Boolean matrix product, and use it to design a new output-sensitive algorithm for listing all triangles in a graph. As a corollary, we obtain an output-sensitive algorithm for listing subgraphs and induced subgraphs isomorphic to an arbitrary fixed pattern graph.

Place, publisher, year, edition, pages
MDPI, 2014. Vol. 7, no 2, p. 243-252
Keywords [en]
Clique, Output-sensitive algorithm, Subgraph, Subgraph isomorphism, Subgraph listing, Time complexity, Triangle
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-211926DOI: 10.3390/a7020243ISI: 000214154600006Scopus ID: 2-s2.0-84907096435OAI: oai:DiVA.org:umu-211926DiVA, id: diva2:1782062
Available from: 2023-07-12 Created: 2023-07-12 Last updated: 2023-07-12Bibliographically approved

Open Access in DiVA

fulltext(214 kB)122 downloads
File information
File name FULLTEXT01.pdfFile size 214 kBChecksum SHA-512
9394818f8a596de50ffb0e86275fecdb941ff1a4c30c5d1a7da0b565a3c3e7992ca708bd30b73928c1404a3a352480f1d4f024e881aa95c05cf271acd020e8cd
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Zechner, Niklas

Search in DiVA

By author/editor
Zechner, Niklas
By organisation
Department of Computing Science
In the same journal
Algorithms
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 122 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 140 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf