Some Reduction Procedure for Computing Pathwidth of Undirected Graphs
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 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E98-D No.3 pp.503-511
- Publication Date
- 2015/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2014FCP0012
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
- Category
Authors
Masataka IKEDA
Kyoto University
Hiroshi NAGAMOCHI
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masataka IKEDA, Hiroshi NAGAMOCHI, "Some Reduction Procedure for Computing Pathwidth of Undirected Graphs" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 3, pp. 503-511, March 2015, doi: 10.1587/transinf.2014FCP0012.
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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014FCP0012/_p
Copy
@ARTICLE{e98-d_3_503,
author={Masataka IKEDA, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Some Reduction Procedure for Computing Pathwidth of Undirected Graphs},
year={2015},
volume={E98-D},
number={3},
pages={503-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.},
keywords={},
doi={10.1587/transinf.2014FCP0012},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Some Reduction Procedure for Computing Pathwidth of Undirected Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 503
EP - 511
AU - Masataka IKEDA
AU - Hiroshi NAGAMOCHI
PY - 2015
DO - 10.1587/transinf.2014FCP0012
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2015
AB - 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.
ER -
English
