Keyword : bounded treewidth


Complexity of the Maximum k-Path Vertex Cover Problem
Eiji MIYANO Toshiki SAITOH Ryuhei UEHARA Tsuyoshi YAGITA Tom C. van der ZANDEN 
Publication:   
Publication Date: 2020/10/01
Vol. E103-A  No. 10 ; pp. 1193-1201
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: complexity theory
Keyword: 
Maximum k-path vertex coverNP-hardnesspolynomial time algorithmsplit graphsbounded treewidth
 Summary | Full Text:PDF(1.9MB)

A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth
Takayoshi SHOUDAI Takashi YAMADA 
Publication:   
Publication Date: 2017/09/01
Vol. E100-A  No. 9 ; pp. 1764-1772
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graph pattern matchingpartial k-tree patternbounded treewidthhyperedge replacementpolynomial time algorithm
 Summary | Full Text:PDF(1.2MB)