Keyword : edge-connectivity


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(670.3KB)

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(770.3KB)

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(341KB)

Approximating a Generalization of Metric TSP
Takuro FUKUNAGA Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2007/02/01
Vol. E90-D  No. 2 ; pp. 432-439
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithms
Keyword: 
approximation algorithmedge-connectivitydegree specificationgraph algorithmmetricnetwork designTSP
 Summary | Full Text:PDF(376.3KB)

Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2007/02/01
Vol. E90-D  No. 2 ; pp. 428-431
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithms
Keyword: 
dynamic graphedge-connectivityextreme vertex setgraph algorithm
 Summary | Full Text:PDF(153.4KB)

A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5 ; pp. 1263-1268
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
algorithmconnectivity augmentationedge-connectivityedge-splittingextreme vertex setsgraph
 Summary | Full Text:PDF(166.6KB)

Maximum-Cover Source-Location Problems
Kenya SUGIHARA Hiro ITO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5 ; pp. 1370-1377
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graphedge-connectivitylocation problempolynomial-time algorithmNP-hard
 Summary | Full Text:PDF(288.5KB)

Increasing the Edge-Connectivity by Contracting a Vertex Subset in Graphs
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2006/02/01
Vol. E89-D  No. 2 ; pp. 744-750
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithm
Keyword: 
algorithmedge-connectivityextreme vertex setsgraphsource location problem
 Summary | Full Text:PDF(532.5KB)

A 2-Approximation Algorithm to (k + 1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph
Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5 ; pp. 1290-1300
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graphsaugmentation problemsedge-connectivityapproximation algorithms
 Summary | Full Text:PDF(387.2KB)

Recent Development of Graph Connectivity Augmentation Algorithms
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Vol. E83-D  No. 3 ; pp. 372-383
Type of Manuscript:  INVITED SURVEY PAPER
Category: Graph Algorithms
Keyword: 
edge-connectivityvertex-connectivityminimum cutsgraphsaugmentation problempolynomial algorithm
 Summary | Full Text:PDF(396.2KB)

A Simple Proof of a Minimum Cut Algorithm and Its Applications
Hiroshi NAGAMOCHI Toshimasa ISHII Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/10/25
Vol. E82-A  No. 10 ; pp. 2231-2236
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
graphedge-connectivityminimum cutflowMA-orderingdynamic tree structure
 Summary | Full Text:PDF(406.5KB)

Computing k-Edge-Connected Components of a Multigraph
Hiroshi NAGAMOCHI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/04/25
Vol. E76-A  No. 4 ; pp. 513-517
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
design of algorithm, computational complexitymultigraphsedge-connectivityconnected componetsmaximum flowsminimum cutspolynomial-time algorithms
 Summary | Full Text:PDF(437.9KB)