研究者詳細 - 大舘　陽太

論文 - 大舘　陽太

分割表示 151 件中 141 - 151 件目／全件表示 >>

Spanning tree congestion of rook's graphs 査読有り

Kyohei Kozawa, Yota Otachi

Discussiones Mathematicae - Graph Theory 31 巻 ( 4 ) 頁： 753 - 761 2011年

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：University of Zielona Gora

Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T ), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Km Kn for any m and n.

DOI： 10.7151/dmgt.1577

Scopus

researchmap

Approximability of the Path-Distance-Width for AT-free Graphs 査読有り

Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE 6986 巻頁： 271 - + 2011年

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：SPRINGER-VERLAG BERLIN

The path-distance-width of a graph measures how close the graph is to a path. We consider the problem of determining the path-distance-width for graphs with chain-like structures such as k-cocomparability graphs, AT-free graphs, and interval graphs. We first show that the problem is NP-hard even for a very restricted subclass of AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for graphs with chain-like structures. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for the class of cochain graphs, which is a subclass of the class of proper interval graphs.

DOI： 10.1007/978-3-642-25870-1_25

Web of Science

researchmap

The carving-width of generalized hypercubes 査読有り

Yohei Kozawa, Yota Otachi, Koichi Yamazaki

DISCRETE MATHEMATICS 310 巻 ( 21 ) 頁： 2867 - 2876 2010年11月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

The carving-width of a graph is the minimum congestion of routing trees for the graph. We determine the carving-width of generalized hypercubes: Hamming graphs, even grids, and tori. Our results extend the result of Chandran and Kavitha [L.S. Chandran, T. Kavitha, The carvingwidth of hypercubes, Discrete Math. 306 (2006) 2270-2274] that determines the carving-width of hypercubes. (C) 2010 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2010.06.039

Web of Science

researchmap

Complexity Results for the Spanning Tree Congestion Problem 査読有り国際共著

Yota Otachi, Hans L. Bodlaender, Erik Jan van Leeuwen

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE 6410 巻頁： 3 - + 2010年

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：SPRINGER-VERLAG BERLIN

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the complexity of this problem. First, we show that for every fixed k and d the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k >= 10. For very small values of k however, the problem becomes polynomially solvable. We also show that it is NP-hard to approximate the spanning tree congestion within a factor better than 11/10. On planar graphs, we prove the problem is NP-hard in general, but solvable in linear time for fixed k.

DOI： 10.1007/978-3-642-16926-7_3

Web of Science

researchmap

On spanning tree congestion of graphs 査読有り

Kyohei Kozawa, Yota Otachi, Koichi Yamazaki

DISCRETE MATHEMATICS 309 巻 ( 13 ) 頁： 4215 - 4224 2009年7月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

Let G be a connected graph and T be a spanning tree of G. For e is an element of E(T), the congestion of e is the number of edges in G connecting two components of T - e. The edge congestion of G in T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes. (C) 2008 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2008.12.021

Web of Science

researchmap

Security number of grid-like graphs 査読有り

Kyohei Kozawa, Yota Otachi, Koichi Yamazaki

DISCRETE APPLIED MATHEMATICS 157 巻 ( 11 ) 頁： 2555 - 2561 2009年6月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

The security number of a graph is the cardinality of a smallest vertex subset of the graph Such that any attack on the subset is defendable. In this paper, we determine the security number of two-dimensional cylinders and tori. This result settles a conjecture of Brigham et al. [R.C. Brigham, R.D. Dutton, S.T. Hedetniemi, Security in graphs, Discrete Appl. Math. 155(2007)1708-1714]. (C) 2009 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2009.03.020

Web of Science

researchmap

Efficient Enumeration of Ordered Trees with k Leaves 査読有り

Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano

WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS 5431 巻頁： 141 - + 2009年

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：SPRINGER-VERLAG BERLIN

In this paper, we give a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n - k) time for each, while our algorithm generates Such trees in O(1) time for each in worst case.

DOI： 10.1007/978-3-642-00202-1_13

Web of Science

researchmap

Random Generation and Enumeration of Bipartite Permutation Graphs 査読有り

Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara

ALGORITHMS AND COMPUTATION, PROCEEDINGS 5878 巻頁： 1104 - + 2009年

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：SPRINGER-VERLAG BERLIN

Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on the reverse search, and it outputs each connected bipartite permutation graph in O(1) time.

DOI： 10.1007/978-3-642-10631-6_111

Web of Science

researchmap

An improved algorithm for the longest induced path problem on k-chordal graphs 査読有り

Tetsuya Ishizeki, Yota Otachi, Koichi Yamazaki

DISCRETE APPLIED MATHEMATICS 156 巻 ( 15 ) 頁： 3057 - 3059 2008年8月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

Gavril [F. Gavril, Algorithms for maximum weight induced paths, Information Processing Letters 81 (2002) 203-208] showed that the length of a longest induced path for graphs having no induced cycles on more than k vertices can be computed in O(n(k)m) time where n and m denote the number of vertices and edges, respectively. In this paper, we present an O(n(k)) time algorithm for the same problem. (C) 2008 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2008.01.019

Web of Science

researchmap

A lower bound for the vertex boundary-width of complete k-ary trees 査読有り

Yota Otachi, Koichi Yamazaki

DISCRETE MATHEMATICS 308 巻 ( 12 ) 頁： 2389 - 2395 2008年6月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

The vertex boundary-width problem (for short VBWP) is to determine the value of vbw(G) = max(1 <= l <= vertical bar V vertical bar) min (S subset of V,vertical bar S vertical bar=l)vertical bar N(S)vertical bar for a given graph G = (V, E), where N(S) = {upsilon is not an element of S vertical bar upsilon is a neighbor of u for some u is an element of S}. In this paper, we give a lower bound for vertex boundary-width of complete k-ary trees. (C) 2007 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2007.05.014

Web of Science

researchmap

Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs 査読有り

Yota Otachi, Yoshio Okamoto, Koichi Yamazaki

DISCRETE APPLIED MATHEMATICS 155 巻 ( 17 ) 頁： 2383 - 2390 2007年10月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

We show that the class of unit grid intersection graphs properly includes both of the classes of interval bigraphs and of P-6-free chordal bipartite graphs. We also demonstrate that the classes of unit grid intersection graphs and of chordal bipartite graphs are incomparable. (C) 2007 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2007.07.010

Web of Science

researchmap

　前のページ - 次のページ　

<大舘 陽太>

論文 - 大舘 陽太

<大舘　陽太>

論文 - 大舘　陽太