根付き有向木次数列問題
スポンサーリンク
概要
- 論文の詳細を見る
Dを有向木とする。ある点rについてdeg^-(r)=0で,それ以外の点vについてdeg^-(v)=1の時,rを根といい,Dを根付き有向木という。非負整数列S=(s_1,s_2,‥‥s_n)が根付き有向木次数列であるとは,すべてのj=1,2,‥‥,nについてdeg^+(v_j)=s_jであるような点v_1,v_2,‥‥,v_nを持つ根付き有向木が存在することである。根付き有向木次数列問題とは,与えられた非負整数列が根付き有向木次数列かどうかを判定することである。本稿では,いくつかの種類の根付き有向木次数列問題と,それらについての線形時間アルゴリズムを提案する。
- 社団法人電子情報通信学会の論文
- 1994-12-09
著者
関連論文
- Some Considerations of Erdos-Sos Conjecture
- プログラミング教育の推進・充実をめざして : 福岡工業短期大学の講義・演習を通しての実践と今後の課題
- 情報処理教育の推進・充実をめざして : 福岡工業短期大学の講義・演習を通しての実践と今後の課題
- The Necessary and Sufficient Conditions of Score Sequence Pair Problems of (r_,r_,r_)-Tournaments
- グラフの1-因子分解を利用した最適スケジューリングアルゴリズム
- Several Approaches of Score Sequence Problems of k-Tournaments
- Score Sequence Pair Problem of Bipartite Tournaments
- Bipartite Digraphical Degree Sequence Problem
- A Consideration of a Score Sequence Problem of a Tournament
- Rooted Tree Sequence Problem
- k-Edge-Connected Multigraphical Degree Sequence Problem
- 点部分集合に関する拡大構成問題
- コンピュータシステムの講義についての考察
- 根付き有向木次数列問題