Keyword : graphs


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

Constant Time Generation of Rectangular Drawings with Exactly n Faces
Satoshi YOSHII Daisuke CHIGIRA Katsuhisa YAMANAKA Shin-ichi NAKANO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/09/01
Vol. E89-A  No. 9 ; pp. 2445-2450
Type of Manuscript:  LETTER
Category: Algorithms and Data Structures
Keyword: 
graphsrectangular drawingsenumeration
 Summary | Full Text:PDF(144.9KB)

Coding Floorplans with Fewer Bits
Katsuhisa YAMANAKA Shin-ichi NAKANO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5 ; pp. 1181-1185
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graphsalgorithms
 Summary | Full Text:PDF(182.3KB)

Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs
Satoshi TAOKA Kazuya WATANABE Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/04/01
Vol. E89-A  No. 4 ; pp. 1049-1057
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphspartitioning problemsheuristic algorithmsoptimal algorithmsdemandsupply
 Summary | Full Text:PDF(437.2KB)

On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree
Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/04/01
Vol. E89-A  No. 4 ; pp. 1042-1048
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphsedge-connectivity of a specified set of verticesaugmentation problemsdegree constraintslinear time algorithms
 Summary | Full Text:PDF(325.4KB)

Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree Increase
Toshiya MASHIMA Takanori FUKUOKA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2006/02/01
Vol. E89-D  No. 2 ; pp. 751-762
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithm
Keyword: 
graphsvertex-connectivity of a specified set of verticesaugmentation problemsdegree constraintslinear time algorithms
 Summary | Full Text:PDF(624.1KB)

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

A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase
Takanori FUKUOKA Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/04/01
Vol. E88-A  No. 4 ; pp. 954-963
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphsconnectivity augmentationvertex-connectivitydegree constraintslinear time algorithms
 Summary | Full Text:PDF(301.5KB)

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

Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs
Miki Shimabara MIYAUCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/08/25
Vol. E83-A  No. 8 ; pp. 1732-1734
Type of Manuscript:  LETTER
Category: Graphs and Networks
Keyword: 
graphsbook embeddingcrossings of edges over the spinepage-number
 Summary | Full Text:PDF(185.1KB)

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

Counting the Number of Paths in a Graph via BDDs
Kyoko SEKINE Hiroshi IMAI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/04/25
Vol. E80-A  No. 4 ; pp. 682-688
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graphspaths#P-completeBDD
 Summary | Full Text:PDF(621.8KB)

An 0(mn) Algorithm for Embedding Graphs into a 3-Page Book
Miki SHIMABARA MIYAUCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1994/03/25
Vol. E77-A  No. 3 ; pp. 521-526
Type of Manuscript:  Special Section PAPER (Special Section on the 6th Karuizawa Workshop on Circuits and Systems)
Category: Graphs, Networks and Matroids
Keyword: 
graphsalgorithmsdata structures and computational complexityVLSI design technology
 Summary | Full Text:PDF(424.3KB)

Fault Tolerance of an Information Disseminating Scheme on a Processor Network
Kumiko KANAI Yoshihide IGARASHI Kinya MIURA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1992/11/25
Vol. E75-A  No. 11 ; pp. 1555-1560
Type of Manuscript:  PAPER
Category: Algorithms, Data Structures and Computational Complexity
Keyword: 
broadcastinggraphsnetworksfault toleranceinformation dissemination
 Summary | Full Text:PDF(555.1KB)

Optimal Schemes for Disseminating Information and Their Fault Tolerance
Yoshihide IGARASHI Kumiko KANAI Kinya MIURA Shingo OSAWA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/01/25
Vol. E75-D  No. 1 ; pp. 22-29
Type of Manuscript:  Special Section PAPER (Special Section on Theoretical Foundations of Computing)
Category: 
Keyword: 
broadcastinggraphsnetworksfault toleranceinformation dissemination
 Summary | Full Text:PDF(748.8KB)