Keyword : polynomial time algorithms


Efficient Algorithms to Augment the Edge-Connectivity of Specified Vertices by One in a Graph
Satoshi TAOKA Toshimasa WATANABE 
Publication:   
Publication Date: 2019/02/01
Vol. E102-A  No. 2 ; pp. 379-388
Type of Manuscript:  Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)
Category: 
Keyword: 
graphsconnectivity augmentationedge-connectivityedge-interchange operationspolynomial time algorithms
 Summary | Full Text:PDF

Reduction of Constraints from Multipartition to Bipartition in Augmenting Edge-Connectivity of a Graph by One
Satoshi TAOKA Tadachika OKI Toshiya MASHIMA Toshimasa WATANABE 
Publication:   
Publication Date: 2018/02/01
Vol. E101-A  No. 2 ; pp. 357-366
Type of Manuscript:  Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)
Category: 
Keyword: 
connectivity augmentation problemsedge-connectivitymultipartition constraintsgraphspolynomial time algorithms
 Summary | Full Text:PDF

A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints
Tadachika OKI Satoshi TAOKA Toshiya MASHIMA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/03/01
Vol. E95-D  No. 3 ; pp. 769-777
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
Category: 
Keyword: 
connectivity augmentation problemsedge-connectivitybipartition constraintsgraphspolynomial time algorithms
 Summary | Full Text:PDF

A 2-Approximation Algorithm 2-ABIS for 2-Vertex-Connectivity Augmentation of Specified Vertices in a Graph
Makoto TAMURA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/04/01
Vol. E86-A  No. 4 ; pp. 822-828
Type of Manuscript:  Special Section PAPER (Special Section of Selected Papers from the 15th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphsaugmentation problemsvertex-connectivityperformance ratiospolynomial time algorithms
 Summary | Full Text:PDF

Graph Augmentation Problems with Degree-Unchangeable Vertices
Toshiya MASHIMA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/03/01
Vol. E84-A  No. 3 ; pp. 781-793
Type of Manuscript:  Special Section PAPER (Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphconnectivity augmentationvertex-connectivitydegree-unchangeable verticespolynomial time algorithms
 Summary | Full Text:PDF

On the Legal Firing Sequence Problem of Petri Nets with Cactus Structure
Toshihiro FUJITO Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/03/25
Vol. E83-A  No. 3 ; pp. 480-486
Type of Manuscript:  Special Section PAPER (Special Section of Selected Papers from the 12th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
Petri netslegal firing sequence problempolynomial time algorithms
 Summary | Full Text:PDF