Some Properties of the Distortion Index/Sequence on All MPRsComputational Complexity of Graph Isomorphism Problem(<特集>Special Issue on Selected Papers from LA Symposium)
スポンサーリンク
概要
- 論文の詳細を見る
The First Most-Parsimonious Reconstruction Problem is: for a given tree (called an el-tree) whose endnodes are evaluated, to find an assignment to all internal nodes of the tree, so as to minimize the total length of the tree. Such assignment is called an MPR. On this problem, an algorithm which enumerates all MPRs on a given el-tree has already given. In this paper, we introduce indicators for each MPR, that is, the distortion index and the distortion sequence, which show how an MPR minimizes each length of subtrees on a rooted el-tree. We characterize the best (or worst) MPR on base of those indicators and a poset induced by those indicators.
- 社団法人電子情報通信学会の論文
- 2002-02-01
著者
-
Narushima Hiroshi
Department Of Information Processing Tokai University Fukuoka Junior College
-
Narushima Hiroshi
Department Of Information And Network Tokai University Junior College
-
MIYAKAWA Kampe
Course in Computer Science and information Mathematics, Graduate School of Electro-Communications, T
-
Miyakawa Kampe
Course In Computer Science And Information Mathematics Graduate School Of Electro-communications The
関連論文
- The Number Tables of the Command Flow Numbers on a Boolean Lattice and a Partition Lattice
- A Tag Type Automaton with a Double Reading Head
- A Move Problem on Weighted Digraphs
- Order Preserving Maps and Classification of Partially Ordered Sets
- A Class of Recurrence Relations on Acyclic Digraphs of Poset Type (Applied Combinatorial Theory and Algorithms)
- Further Results on Order Maps
- Some Properties of the Distortion Index/Sequence on All MPRsComputational Complexity of Graph Isomorphism Problem(Special Issue on Selected Papers from LA Symposium)
- The Number Table of the Coefficients of the Command Flow Polynomial on a Boolean Lattice
- An Asymptotic Formula for the Number of Chains in a Boolean Lattice : a survey and another proof
- Order Maps and Cardinal Congruence Classes on Partitions
- A Necessary and Sufficient Condition for a Simplicial Complex to be an Order Complex and its Checking Computer Algorithm
- A Proof of Stanley's Characterization for a Simplicial Complex to be an Order Complex
- The Order Complexes on the 2-sphere
- The Lightest Totalization of an Endnode Labelling of a Non-tree Graph II
- Analysis of the Command Flow Numbers I : Boolean Lattices (Graphs and Combinatorics III)
- A Survey of Enumerative Combinatorial Theory and A Problem
- On a Hereditary Poset
- A Method for Counting the Number of Chains in a Partially Ordered Set