Downloads: 123

Files in This Item:
File Description SizeFormat 
transinf.2014FCP0012.pdf1.04 MBAdobe PDFView/Open
Full metadata record
DC FieldValueLanguage
dc.contributor.authorIKEDA, Masatakaja
dc.contributor.authorNAGAMOCHI, Hiroshija
dc.contributor.alternative永持, 仁ja
dc.date.accessioned2015-04-01T05:39:58Z-
dc.date.available2015-04-01T05:39:58Z-
dc.date.issued2015-03-01-
dc.identifier.issn0916-8532ja
dc.identifier.urihttp://hdl.handle.net/2433/196656-
dc.description.abstractComputing an invariant of a graph such as treewidth and pathwidth is one of the fundamental problems in graph algorithms. In general, determining the pathwidth of a graph is NP-hard. In this paper, we propose several reduction methods for decreasing the instance size without changing the pathwidth, and implemented the methods together with an exact algorithm for computing pathwidth of graphs. Our experimental results show that the number of vertices in all chemical graphs in NCI database decreases by our reduction methods by 53.81% in average.ja
dc.format.mimetypeapplication/pdfja
dc.language.isoengja
dc.publisherInstitute of Electronics, Information and Communication Engineers(IEICE)ja
dc.publisher.alternative電子情報通信学会-
dc.rights© 2015 The Institute of Electronics, Information and Communication Engineersja
dc.subjectpathwidthja
dc.subjectexact algorithmsja
dc.subjectgraphsja
dc.subjectchemical graphsja
dc.titleSome Reduction Procedure for Computing Pathwidth of Undirected Graphsja
dc.type.niitypeJournal Articleja
dc.identifier.ncidAA10826272ja
dc.identifier.jtitleIEICE Transactions on Information and Systemsja
dc.identifier.volumeE98.Dja
dc.identifier.issue3ja
dc.identifier.spage503ja
dc.identifier.epage511ja
dc.relation.doi10.1587/transinf.2014FCP0012ja
dc.textversionpublisherja
Appears in Collections:Journal Articles

Show simple item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.