Partitions of Graphs into Chains of the Minimum Block Number

スポンサーリンク

概要

• 論文の詳細を見る

• We deal in this paper partitions of digraphs into chains. The partition is also called a path cover [2,6] or a linearization [1]. We introduce an equivalent relation over the edges, and also introduce components of the digraphs derived by the relation. We show that the finding problem of the chain partition of the digraph with the minimum chain (block) number is partitioned to the problems of the components. From the result and [3], it is also shown that there exists an O(m^5/2) time algorithm that obtain a chain partition of digraphs with the minimum block number.

• 東海大学の論文
• 1983-03-31

著者

• Yaku Takeo

  Department Of Computer Science And System Analysis Nihon University

• Yaku Takeo

  Department Of Mathematical Sciences Faculty Of Science Tokai University

関連論文

• Visual Software Development Environment Based on Graph Grammars
• Generation of the Hichart Program Diagrams
• Partitions of Graphs into Chains of the Minimum Block Number
• A Control Structure between Iteration and Recursion
• Wiring a Turing Machine in the Cellular Automaton and the Surjectivity Problem for a Parallel Map

スポンサーリンク