IEICE Trans

Keyword : edge-connectivity

Enumerating Highly-Edge-Connected Spanning Subgraphs Katsuhisa YAMANAKA Yasuko MATSUI Shin-ichi NAKANO
Publication: Publication Date: 2019/09/01 Vol. E102-A No. 9 ; pp. 1002-1006 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Graph algorithms Keyword: enumeration, algorithm, spanning subgraph, edge-connectivity,
	Summary \| Full Text:PDF(741.6KB)

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: graphs, connectivity augmentation, edge-connectivity, edge-interchange operations, polynomial 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 problems, edge-connectivity, multipartition constraints, graphs, polynomial 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 problems, edge-connectivity, bipartition constraints, graphs, polynomial 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 algorithm, edge-connectivity, degree specification, graph algorithm, metric, network design, TSP,
	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 graph, edge-connectivity, extreme vertex set, graph 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: algorithm, connectivity augmentation, edge-connectivity, edge-splitting, extreme vertex sets, graph,
	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: graph, edge-connectivity, location problem, polynomial-time algorithm, NP-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: algorithm, edge-connectivity, extreme vertex sets, graph, source 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: graphs, augmentation problems, edge-connectivity, approximation 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-connectivity, vertex-connectivity, minimum cuts, graphs, augmentation problem, polynomial 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: graph, edge-connectivity, minimum cut, flow, MA-ordering, dynamic 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 complexity, multigraphs, edge-connectivity, connected componets, maximum flows, minimum cuts, polynomial-time algorithms,
	Summary \| Full Text:PDF(437.9KB)