Keyword : graph algorithm


Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints
Yu NAKAHATA Jun KAWAHARA Takashi HORIYAMA Shoji KASAHARA 
Publication:   
Publication Date: 2018/09/01
Vol. E101-A  No. 9 ; pp. 1363-1374
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graph algorithmgraph partitioningdecision diagramfrontier-based searchenumeration problem
 Summary | Full Text:PDF(1.8MB)

Power of Enumeration — Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation
Shin-ichi MINATO 
Publication:   
Publication Date: 2017/08/01
Vol. E100-D  No. 8 ; pp. 1556-1562
Type of Manuscript:  INVITED PAPER (Special Section on Multiple-Valued Logic and VLSI Computing)
Category: 
Keyword: 
BDDZDDdiscrete structuregraph algorithm
 Summary | Full Text:PDF(2.3MB)

Reconfiguration of Vertex Covers in a Graph
Takehiro ITO Hiroyuki NOOKA Xiao ZHOU 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/03/01
Vol. E99-D  No. 3 ; pp. 598-606
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)
Category: 
Keyword: 
combinatorial reconfigurationeven-hole-free graphgraph algorithmvertex cover
 Summary | Full Text:PDF(410.2KB)

Algorithms for the Independent Feedback Vertex Set Problem
Yuma TAMURA Takehiro ITO Xiao ZHOU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2015/06/01
Vol. E98-A  No. 6 ; pp. 1179-1188
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
fixed parameter tractabilitygraph algorithmindependent feedback vertex set
 Summary | Full Text:PDF(939KB)

The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
Tatsuhiko HATANAKA Takehiro ITO Xiao ZHOU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2015/06/01
Vol. E98-A  No. 6 ; pp. 1168-1178
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graph algorithmlist coloringpathwidthPSPACE-completereachability on solution spacereconfiguration
 Summary | Full Text:PDF(957.4KB)

Constant Time Enumeration of Subtrees with Exactly k Nodes in a Tree
Kunihiro WASA Yusaku KANETA Takeaki UNO Hiroki ARIMURA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2014/03/01
Vol. E97-D  No. 3 ; pp. 421-430
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—)
Category: Graph Algorithms, Knowledge Discovery
Keyword: 
graph algorithmenumeration algorithmconstant delay enumerationmotif discoverytree mining
 Summary | Full Text:PDF(561.3KB)

On the Minimum Caterpillar Problem in Digraphs
Taku OKADA Akira SUZUKI Takehiro ITO Xiao ZHOU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/03/01
Vol. E97-A  No. 3 ; pp. 848-857
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
bounded treewidth graphcaterpillardynamic programminggraph algorithminapproximability
 Summary | Full Text:PDF(1.1MB)

An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
Takehiro ITO Kazuto KAWAMURA Xiao ZHOU 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/03/01
Vol. E95-D  No. 3 ; pp. 737-745
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
Category: 
Keyword: 
graph algorithmlist edge-coloringreachability on solution spacereconfiguration problemtree
 Summary | Full Text:PDF(357.2KB)

Enumerating All Rooted Trees Including k Leaves
Masanobu ISHIKAWA Katsuhisa YAMANAKA Yota OTACHI Shin-ichi NAKANO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/03/01
Vol. E95-D  No. 3 ; pp. 763-768
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
Category: 
Keyword: 
graph algorithmenumerationrooted treefamily tree
 Summary | Full Text:PDF(258.3KB)

Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs
Bingbing ZHUANG Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2011/02/01
Vol. E94-D  No. 2 ; pp. 211-219
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
Category: 
Keyword: 
enumeration algorithmgraph algorithmplanar graphouterplanar graphsymmetry
 Summary | Full Text:PDF(722.6KB)

Approximation to the Minimum Cost Edge Installation Problem
Ehab MORSY Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2010/04/01
Vol. E93-A  No. 4 ; pp. 778-786
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
approximation algorithmgraph algorithmrouting problemnetwork optimization
 Summary | Full Text:PDF(250KB)

Approximation Algorithms for Multicast Routings in a Network with Multi-Sources
Ehab MOSRY Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/05/01
Vol. E90-A  No. 5 ; pp. 900-906
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
approximation algorithmfacility location problemgraph algorithmmulticast routing problemnetwork optimizationtree cover
 Summary | Full Text:PDF(195.1KB)

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)

Approximating the Minmax Rooted-Subtree Cover Problem
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5 ; pp. 1335-1338
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
approximation algorithmgraph algorithmpartitionsubtree cover problemtraveling salesman problem
 Summary | Full Text:PDF(100.8KB)

Computational Results for Gaussian Moat Problem
Nobuyuki TSUCHIMURA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5 ; pp. 1267-1273
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graph algorithmGaussian primeparallel computing
 Summary | Full Text:PDF(867.5KB)

On 2-Approximation to the Vertex-Connectivity in Graphs
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/01/01
Vol. E88-D  No. 1 ; pp. 12-16
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
graph algorithmapproximation algorithmvertex-connectivityMA orderingsminimum degree
 Summary | Full Text:PDF(128.7KB)

The Design and Evaluation of Data-Dependent Hardware for Subgraph Isomorphism Problem
Shoji YAMAMOTO Shuichi ICHIKAWA Hiroshi YAMAMOTO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/08/01
Vol. E87-D  No. 8 ; pp. 2038-2047
Type of Manuscript:  Special Section PAPER (Special Section on Reconfigurable Systems)
Category: Recornfigurable Systems
Keyword: 
FPGAcustom circuitgraph algorithmNP-completepartial evaluation
 Summary | Full Text:PDF(472.8KB)

Approximability of the Minimum Maximal Matching Problem in Planar Graphs
Hiroshi NAGAMOCHI Yukihiro NISHIDA Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/12/01
Vol. E86-A  No. 12 ; pp. 3251-3258
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
graph algorithmapproximation algorithmmatchingplanar graphseparator
 Summary | Full Text:PDF(259.3KB)

Data Dependent Circuit for Subgraph Isomorphism Problem
Shuichi ICHIKAWA Shoji YAMAMOTO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/05/01
Vol. E86-D  No. 5 ; pp. 796-802
Type of Manuscript:  Special Section PAPER (Special Issue on Reconfigurable Computing)
Category: 
Keyword: 
NP-completecustom circuitFPGAgraph algorithm
 Summary | Full Text:PDF(257.7KB)

Traversing Graphs in Small Space
Seinosuke TODA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Vol. E83-D  No. 3 ; pp. 392-396
Type of Manuscript:  INVITED SURVEY PAPER
Category: Graph Algorithms
Keyword: 
st-connectivity problemlogarithmic spacegraph algorithmrandomizationcomputational complexity theory
 Summary | Full Text:PDF(228.6KB)

Minimum Cut Linear Arrangement of p-q Dags for VLSI Layout of Adder Trees
Kazuyoshi TAKAGI Naofumi TAKAGI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/05/25
Vol. E82-A  No. 5 ; pp. 767-774
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graph algorithmminimum cut linear arrangementVLSI layoutadder treemultiplier
 Summary | Full Text:PDF(690KB)