<?xml version="1.0" encoding="ISO-8859-1"?>
<metadatalist>
	<metadata ReferenceType="Conference Proceedings">
		<site>sibgrapi.sid.inpe.br 802</site>
		<identifier>6qtX3pFwXQZeBBx/GHBVm</identifier>
		<repository>sid.inpe.br/banon/2005/07.10.17.42</repository>
		<lastupdate>2005:07.10.03.00.00 sid.inpe.br/banon/2001/03.30.15.38 administrator</lastupdate>
		<metadatarepository>sid.inpe.br/banon/2005/07.10.17.42.13</metadatarepository>
		<metadatalastupdate>2020:02.19.03.19.10 sid.inpe.br/banon/2001/03.30.15.38 administrator {D 2005}</metadatalastupdate>
		<citationkey>AndradeNetoGued:2005:LiAlEx</citationkey>
		<title>A linear algorithm for exact pattern matching in planar subdivisions</title>
		<format>On-line</format>
		<year>2005</year>
		<date>9-12 Oct. 2005</date>
		<numberoffiles>1</numberoffiles>
		<size>270 KiB</size>
		<author>Andrade Neto, Pedro Ribeiro de,</author>
		<author>Guedes, André Luiz Pires,</author>
		<affiliation>Federal University of Paraná</affiliation>
		<editor>Rodrigues, Maria Andréia Formico,</editor>
		<editor>Frery, Alejandro César,</editor>
		<e-mailaddress>pedrorib@yahoo.com</e-mailaddress>
		<conferencename>Brazilian Symposium on Computer Graphics and Image Processing, 18 (SIBGRAPI)</conferencename>
		<conferencelocation>Natal</conferencelocation>
		<booktitle>Proceedings</booktitle>
		<publisher>IEEE Computer Society</publisher>
		<publisheraddress>Los Alamitos</publisheraddress>
		<transferableflag>1</transferableflag>
		<contenttype>External Contribution</contenttype>
		<tertiarytype>Full Paper</tertiarytype>
		<keywords>sub-isomorphism, planar subdivisions.</keywords>
		<abstract>Graph sub-isomorphism is a very common approach to solving pattern search problems, but this is a NP-complete problem. This way, it is necessary to invest in research of approximate solutions, or in special cases of the problem. Planar subdivisions can be considered as a special case of graphs, because, in addition to nodes and edges, there is a more rigid topology in relation to the order of the edges, arising to the concept of face. This work presents a linear algorithm for pattern search in planar subdivisions. The presented algorithm is based on a hybrid approach between the dual and the region adjacency graph (RAG) to represent the patterns, saving any additional storage cost. Thus, the patterns are looked over the search subdivision, using a region growing algorithm.</abstract>
		<language>en</language>
		<targetfile>andradep_matchsubdivisions.pdf</targetfile>
		<usergroup>pedrorib administrator</usergroup>
		<visibility>shown</visibility>
		<hostcollection>sid.inpe.br/banon/2001/03.30.15.38</hostcollection>
		<lasthostcollection>sid.inpe.br/banon/2001/03.30.15.38</lasthostcollection>
		<url>http://sibgrapi.sid.inpe.br/rep-/sid.inpe.br/banon/2005/07.10.17.42</url>
	</metadata>
</metadatalist>