Shigeru MASUYAMA


A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Outerplanar Graphs
Shin-ichi NAKAYAMA Shigeru MASUYAMA 
Publication:   
Publication Date: 2017/03/01
Vol. E100-D  No. 3  pp. 434-443
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
Category: 
Keyword: 
spanning treeouterplanar graphalgorithm
 Summary | Full Text:PDF(1.1MB)

A Linear Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Cographs
Shin-ichi NAKAYAMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/10/01
Vol. E99-D  No. 10  pp. 2574-2584
Type of Manuscript:  PAPER
Category: Fundamentals of Information Systems
Keyword: 
spanning treecographalgorithm
 Summary | Full Text:PDF(1.5MB)

Algorithm for Identifying the Maximum Detour Hinge Vertices of a Permutation Graph
Hirotoshi HONMA Yoko NAKAJIMA Yuta IGARASHI Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2015/06/01
Vol. E98-A  No. 6  pp. 1161-1167
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
design and analysis of algorithmsintersection graphsmaximum detour hinge vertex problempermutation graph
 Summary | Full Text:PDF(589.8KB)

Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs
Hirotoshi HONMA Yoko NAKAJIMA Yuta IGARASHI Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/06/01
Vol. E97-A  No. 6  pp. 1365-1369
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
design and analysis of algorithmsmaximum detour hinge vertex problemintersection graphsinterval graphs
 Summary | Full Text:PDF(232KB)

Efficient Randomized Byzantine Fault-Tolerant Replication Based on Special Valued Coin Tossing
Junya NAKAMURA Tadashi ARARAGI Shigeru MASUYAMA Toshimitsu MASUZAWA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2014/02/01
Vol. E97-D  No. 2  pp. 231-244
Type of Manuscript:  PAPER
Category: Dependable Computing
Keyword: 
Byzantine fault tolerancestate machine replicationByzantine agreementconsensusasynchronous distributed system
 Summary | Full Text:PDF(1.4MB)

A Method of Parallelizing Consensuses for Accelerating Byzantine Fault Tolerance
Junya NAKAMURA Tadashi ARARAGI Toshimitsu MASUZAWA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2014/01/01
Vol. E97-D  No. 1  pp. 53-64
Type of Manuscript:  PAPER
Category: Dependable Computing
Keyword: 
Byzantine fault toleranceasynchronous distributed systemagreementconsensusstate machine replication
 Summary | Full Text:PDF(993.4KB)

A Linear-Time Algorithm for Constructing a Spanning Tree on Circular Trapezoid Graphs
Hirotoshi HONMA Yoko NAKAJIMA Haruka AOSHIMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2013/06/01
Vol. E96-A  No. 6  pp. 1051-1058
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
design and analysis of algorithmsintersection graphscircular trapezoid graphsspanning tree problem
 Summary | Full Text:PDF(1MB)

Linear Time Algorithms for Finding Articulation and Hinge Vertices of Circular Permutation Graphs
Hirotoshi HONMA Kodai ABE Yoko NAKAJIMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Vol. E96-D  No. 3  pp. 419-425
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
design and analysis of algorithmsarticulation verticeshinge verticescircular permutation graphs
 Summary | Full Text:PDF(468.2KB)

An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph
Hirotoshi HONMA Yutaro KITAMURA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2011/06/01
Vol. E94-A  No. 6  pp. 1381-1385
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
design and analysis of algorithmsfeedback vertex settrapezoid graphsNP-hard
 Summary | Full Text:PDF(168.3KB)

Assigning Polarity to Causal Information in Financial Articles on Business Performance of Companies
Hiroyuki SAKAI Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2009/12/01
Vol. E92-D  No. 12  pp. 2341-2350
Type of Manuscript:  Special Section PAPER (Special Section on Natural Language Processing and its Applications)
Category: Document Analysis
Keyword: 
polarity assignmenttext miningcausal informationknowledge extractioninformation extraction
 Summary | Full Text:PDF(589KB)

An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs
Hirotoshi HONMA Saki HONMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2009/02/01
Vol. E92-D  No. 2  pp. 141-148
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
parallel algorithmsgraph algorithmscircular permutation graphsspanning tree
 Summary | Full Text:PDF(615.5KB)

Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph Kn
Peng CHENG Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/09/01
Vol. E91-A  No. 9  pp. 2314-2321
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
complete graphconnected spanning subgraphlog concave sequencenetwork reliability polynomial
 Summary | Full Text:PDF(336.9KB)

An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs
Hirotoshi HONMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/09/01
Vol. E91-A  No. 9  pp. 2296-2300
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
parallel algorithmstrapezoid graphsspanning forestspanning tree
 Summary | Full Text:PDF(300.4KB)

An Informative DOM Subtree Identification Method from Web Pages in Unfamiliar Web Sites
Masanobu TSURUTA Hiroyuki SAKAI Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/04/01
Vol. E91-D  No. 4  pp. 986-989
Type of Manuscript:  Special Section LETTER (Special Section on Knowledge-Based Software Engineering)
Category: 
Keyword: 
informative region identificationWeb documentDOMlayout analysis
 Summary | Full Text:PDF(252.6KB)

Cause Information Extraction from Financial Articles Concerning Business Performance
Hiroyuki SAKAI Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/04/01
Vol. E91-D  No. 4  pp. 959-968
Type of Manuscript:  Special Section PAPER (Special Section on Knowledge-Based Software Engineering)
Category: Knowledge Engineering
Keyword: 
cause informationcausal expressionknowledge extractioninformation extraction
 Summary | Full Text:PDF(604.8KB)

Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph
Peng CHENG Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/02/01
Vol. E91-D  No. 2  pp. 178-186
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graphs and Networks
Keyword: 
multigraphthe number of connected spanning subgraphsnetwork reliability polynomialinequality
 Summary | Full Text:PDF(302.9KB)

An Optimal Parallel Algorithm for Finding All Hinge Vertices of a Circular-Arc Graph
Hirotoshi HONMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/01/01
Vol. E91-A  No. 1  pp. 383-391
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
parallel algorithmscircular-arc graphshinge verticesnetwork reliability
 Summary | Full Text:PDF(390.2KB)

A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs
Shin-ichi NAKAYAMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2006/08/01
Vol. E89-D  No. 8  pp. 2357-2363
Type of Manuscript:  INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
Category: 
Keyword: 
algorithmvertex rankingspanning treeouterplanar graph
 Summary | Full Text:PDF(379.8KB)

Formulation of Mobile Agent Allocation and Its Strong NP-Completeness
Atsushi SASAKI Tadashi ARARAGI Shigeru MASUYAMA Keizo MIYATA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/05/01
Vol. E88-D  No. 5  pp. 1060-1063
Type of Manuscript:  LETTER
Category: Complexity Theory
Keyword: 
strong NP-completenessmobile agentscommunication costsubgraph isomorphismload balancing
 Summary | Full Text:PDF(123KB)

Multiple Document Summarization System GOLD
Tatsumi YOSHIDA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/09/01
Vol. E86-D  No. 9  pp. 1719-1727
Type of Manuscript:  Special Section PAPER (Special Issue on Text Processing for Information Access)
Category: 
Keyword: 
NTCIRsummarizationmultiple document
 Summary | Full Text:PDF(913.5KB)

A Statistical Method for Acquiring Knowledge about the Abbreviation Possibility of Some of Multiple Adnominal Phrases
Hiroyuki SAKAI Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/09/01
Vol. E86-D  No. 9  pp. 1710-1718
Type of Manuscript:  Special Section PAPER (Special Issue on Text Processing for Information Access)
Category: 
Keyword: 
abbreviation of multiple adnominal phrasescorpussummarizationmutual information
 Summary | Full Text:PDF(194.6KB)

Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph
Peng CHENG Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Vol. E86-A  No. 5  pp. 1027-1033
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
spanning treesthe number of connected spanning subgraphsthe average number of spanning trees in connected spanning subgraphsall-terminal network reliability polynomial
 Summary | Full Text:PDF(243.5KB)

An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs
Shin-ichi NAKAYAMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Vol. E86-A  No. 5  pp. 1019-1026
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
algorithmvertex rankingspanning treeinterval graph
 Summary | Full Text:PDF(301.5KB)

A Parallel Algorithm for Finding All Hinge Vertices of a Trapezoid Graph
Hirotoshi HONMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/05/01
Vol. E85-A  No. 5  pp. 1031-1040
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
parallel algorithmtrapezoid graphshinge verticesnetwork reliability
 Summary | Full Text:PDF(688KB)

A Parallel Algorithm for Finding All Hinge Vertices of an Interval Graph
Hirotoshi HONMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/03/01
Vol. E84-D  No. 3  pp. 419-423
Type of Manuscript:  LETTER
Category: Algorithms
Keyword: 
parallel algorithminterval graphshinge verticesshortest paths
 Summary | Full Text:PDF(211KB)

An Algorithm for Finding Two Edge-Disjoint Paths in Tournaments
Shin-ichi NAKAYAMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/12/25
Vol. E83-A  No. 12  pp. 2672-2678
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
edge-disjoint pathtournament graphalgorithm
 Summary | Full Text:PDF(370.2KB)

What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? --Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples--
Shigeru MASUYAMA Shin-ichi NAKAYAMA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Vol. E83-D  No. 3  pp. 541-549
Type of Manuscript:  INVITED SURVEY PAPER
Category: Parallel and Distributed Algorithms
Keyword: 
parallel graph algorithmsstructure and complexityouterplanar graphtrapezoid graphin-tournament graph
 Summary | Full Text:PDF(1.1MB)

UGLR Parser for Phrase Structure Languages as an Extension of GLR Parser
Hiromitsu SHIINA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/05/25
Vol. E82-A  No. 5  pp. 792-797
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
GLR parserphrase structure grammarphrase structure language
 Summary | Full Text:PDF(627.9KB)

Parallel Algorithms for Finding a Hamiltonian Path and a Hamiltonian Cycle in an In-Tournament Graph
Shin-ichi NAKAYAMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1998/05/25
Vol. E81-A  No. 5  pp. 757-767
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
parallel algorithmsHamiltonian pathHamiltonian cyclein-tournament
 Summary | Full Text:PDF(970KB)

On the Ambiguity Reduction Ability of a Probabilistic Context-Free Grammar
Kiyotaka ATSUMI Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1998/05/25
Vol. E81-A  No. 5  pp. 825-831
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
probabilistic context-free grammarambiguityambiguity reduction ability
 Summary | Full Text:PDF(562.5KB)

An Efficient Parallel Parsing Algorithm for Context-Free Languages Based on Earley's Method
Kiyotaka ATSUMI Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/04/25
Vol. E79-A  No. 4  pp. 547-552
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
parallel parsingcontext-free grammartheoretically efficient parallel algorithmEarley's method
 Summary | Full Text:PDF(522.2KB)

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)

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)

The Computational Complexity of the m-Center Problems on the Plane
Shigeru MASUYAMA Toshihide IBARAKI Toshiharu HASEGAWA 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1981/02/25
Vol. E64-E  No. 2  pp. 57-64
Type of Manuscript:  PAPER
Category: Miscellaneous
Keyword: 
 Summary | Full Text:PDF(430.5KB)