Keyword : polynomial time algorithm


Computational Complexity and Polynomial Time Procedure of Response Property Problem in Workflow Nets
Muhammad Syafiq BIN AB MALEK Mohd Anuaruddin BIN AHMADON Shingo YAMAGUCHI 
Publication:   
Publication Date: 2018/06/01
Vol. E101-D  No. 6 ; pp. 1503-1510
Type of Manuscript:  Special Section PAPER (Special Section on Formal Approaches)
Category: Formal Approaches
Keyword: 
the response propertyPetri netprocess treecomputational complexitypolynomial time algorithm
 Summary | Full Text:PDF(609.5KB)

Polynomial Time Learnability of Graph Pattern Languages Defined by Cographs
Takayoshi SHOUDAI Yuta YOSHIMURA Yusuke SUZUKI Tomoyuki UCHIDA Tetsuhiro MIYAHARA 
Publication:   
Publication Date: 2018/03/01
Vol. E101-D  No. 3 ; pp. 582-592
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theoretical Computer Science —)
Category: 
Keyword: 
graph pattern matchingcograph patternpolynomial time algorithminductive inferencecomputational learning theory
 Summary | Full Text:PDF(687.5KB)

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)

Polynomial Time Inductive Inference of Languages of Ordered Term Tree Patterns with Height-Constrained Variables from Positive Data
Takayoshi SHOUDAI Kazuhide AIKOH Yusuke SUZUKI Satoshi MATSUMOTO Tetsuhiro MIYAHARA Tomoyuki UCHIDA 
Publication:   
Publication Date: 2017/03/01
Vol. E100-A  No. 3 ; pp. 785-802
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
tree structured patternheight-constrained variablepolynomial time algorithminductive inferencecomputational learning theory
 Summary | Full Text:PDF(2.3MB)

An Efficient Pattern Matching Algorithm for Ordered Term Tree Patterns
Yusuke SUZUKI Takayoshi SHOUDAI Tomoyuki UCHIDA Tetsuhiro MIYAHARA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2015/06/01
Vol. E98-A  No. 6 ; pp. 1197-1211
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
ordered tree structured patterngraph pattern matching algorithmpolynomial time algorithmNP-completeness
 Summary | Full Text:PDF(2MB)

Polynomial Time Verification of Reachability in Sound Extended Free-Choice Workflow Nets
Shingo YAMAGUCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/02/01
Vol. E97-A  No. 2 ; pp. 468-475
Type of Manuscript:  Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)
Category: 
Keyword: 
Petri networkflow netreachabilityextended free-choicewell-structuredpolynomial time algorithm
 Summary | Full Text:PDF(605.8KB)

Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs
Masashi KIYOMI Toshiki SAITOH Ryuhei UEHARA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Vol. E96-D  No. 3 ; pp. 426-432
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
the graph reconstruction conjecturepermutation graphspolynomial time algorithm
 Summary | Full Text:PDF(540.1KB)

An Algorithm for Node-to-Node Disjoint Paths Problem in Burnt Pancake Graphs
Keiichi KANEKO Naoki SAWADA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2007/01/01
Vol. E90-D  No. 1 ; pp. 306-313
Type of Manuscript:  PAPER
Category: Dependable Computing
Keyword: 
burnt pancake graphsnode-to-node disjoint paths problemcontainer probleminternally disjoint pathspolynomial time algorithm
 Summary | Full Text:PDF(534.8KB)

On the Edge Importance Using Its Traffic Based on a Distribution Function along Shortest Paths in a Network
Peng CHENG Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1995/03/25
Vol. E78-A  No. 3 ; pp. 440-443
Type of Manuscript:  LETTER
Category: Graphs, Networks and Matroids
Keyword: 
graph theoryshortest pathedge importance with respect to trafficdistribution functionpolynomial time algorithm
 Summary | Full Text:PDF(290.9KB)

On the Proper-Path-Decomposition of Trees
Atsushi TAKAHASHI Shuichi UENO Yoji KAJITANI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1995/01/25
Vol. E78-A  No. 1 ; pp. 131-136
Type of Manuscript:  LETTER
Category: Graphs, Networks and Matroids
Keyword: 
proper-path-widthproper-path-decompositionpath-widthpath-decompositionpolynomial time algorithm
 Summary | Full Text:PDF(432.9KB)

Computing the Expected Maximum Number of Vertex-Disjoint s-t Paths in a Probabilistic Basically Series-Parallel Digraph
Peng CHENG Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/12/25
Vol. E76-A  No. 12 ; pp. 2089-2094
Type of Manuscript:  PAPER
Category: Graphs, Networks and Matroids
Keyword: 
probabilistic graphexpected maximum number of vertex-disjoint s-t pathsseries-parallel undirected graphbasically series-parallel directed graphpolynomial time algorithm
 Summary | Full Text:PDF(465.6KB)

Polynomial Time Inference of Unions of Two Tree Pattern Languages
Hiroki ARIMURA Takeshi SHINOHARA Setsuko OTSUKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/07/25
Vol. E75-D  No. 4 ; pp. 426-434
Type of Manuscript:  Special Section PAPER (Special Issue on Algorithmic Learning Theory)
Category: 
Keyword: 
inductive inferencelearningpattern languagepolynomial time algorithminference from positive data
 Summary | Full Text:PDF(855.9KB)

An Approximate Algorithm for Decision Tree Design
Satoru OHTA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1992/05/25
Vol. E75-A  No. 5 ; pp. 622-630
Type of Manuscript:  PAPER
Category: Optimization Techniques
Keyword: 
decision treepattern recognitionoptimizationapproximation algorithmstatistical decision problemsource codingpolynomial time algorithm
 Summary | Full Text:PDF(716.5KB)