IEICE Trans

Keyword : polynomial time algorithm

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 cover, NP-hardness, polynomial time algorithm, split graphs, bounded treewidth,
	Summary \| Full Text:PDF

An Efficient Pattern Matching Algorithm for Unordered Term Tree Patterns of Bounded Dimension Takayoshi SHOUDAI Tetsuhiro MIYAHARA Tomoyuki UCHIDA Satoshi MATSUMOTO Yusuke SUZUKI
Publication: Publication Date: 2018/09/01 Vol. E101-A No. 9 ; pp. 1344-1354 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: tree structured pattern, graph pattern matching algorithm, polynomial time algorithm, NP-completeness,
	Summary \| Full Text:PDF

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 property, Petri net, process tree, computational complexity, polynomial time algorithm,
	Summary \| Full Text:PDF

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 matching, cograph pattern, polynomial time algorithm, inductive inference, computational learning theory,
	Summary \| Full Text:PDF

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 matching, partial k-tree pattern, bounded treewidth, hyperedge replacement, polynomial time algorithm,
	Summary \| Full Text:PDF

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 pattern, height-constrained variable, polynomial time algorithm, inductive inference, computational learning theory,
	Summary \| Full Text:PDF

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 pattern, graph pattern matching algorithm, polynomial time algorithm, NP-completeness,
	Summary \| Full Text:PDF

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 net, workflow net, reachability, extended free-choice, well-structured, polynomial time algorithm,
	Summary \| Full Text:PDF

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 conjecture, permutation graphs, polynomial time algorithm,
	Summary \| Full Text:PDF

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 graphs, node-to-node disjoint paths problem, container problem, internally disjoint paths, polynomial time algorithm,
	Summary \| Full Text:PDF

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 theory, shortest path, edge importance with respect to traffic, distribution function, polynomial time algorithm,
	Summary \| Full Text:PDF

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-width, proper-path-decomposition, path-width, path-decomposition, polynomial time algorithm,
	Summary \| Full Text:PDF

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 graph, expected maximum number of vertex-disjoint s-t paths, series-parallel undirected graph, basically series-parallel directed graph, polynomial time algorithm,
	Summary \| Full Text:PDF

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 inference, learning, pattern language, polynomial time algorithm, inference from positive data,
	Summary \| Full Text:PDF

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 tree, pattern recognition, optimization, approximation algorithm, statistical decision problem, source coding, polynomial time algorithm,
	Summary \| Full Text:PDF