Downloads: 119

Files in This Item:
File Description SizeFormat 
transinf.2014FCP0012.pdf1.04 MBAdobe PDFView/Open
Title: Some Reduction Procedure for Computing Pathwidth of Undirected Graphs
Authors: IKEDA, Masataka
NAGAMOCHI, Hiroshi  kyouindb  KAKEN_id
Author's alias: 永持, 仁
Keywords: pathwidth
exact algorithms
graphs
chemical graphs
Issue Date: 1-Mar-2015
Publisher: Institute of Electronics, Information and Communication Engineers(IEICE)
Journal title: IEICE Transactions on Information and Systems
Volume: E98.D
Issue: 3
Start page: 503
End page: 511
Abstract: Computing 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.
Rights: © 2015 The Institute of Electronics, Information and Communication Engineers
URI: http://hdl.handle.net/2433/196656
DOI(Published Version): 10.1587/transinf.2014FCP0012
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


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