
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Some Reduction Procedure for Computing Pathwidth of Undirected Graphs
Masataka IKEDA Hiroshi NAGAMOCHI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E98D
No.3
pp.503511 Publication Date: 2015/03/01 Online ISSN: 17451361
DOI: 10.1587/transinf.2014FCP0012 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer ScienceNew Spirits in Theory of Computation and Algorithm) Category: Keyword: pathwidth, exact algorithms, graphs, chemical graphs,
Full Text: PDF>>
Summary:
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 NPhard. 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.

