Partitions, Functions and the Arc-Coloring of Digraphs(Graphs and Networks)
スポンサーリンク
概要
- 論文の詳細を見る
Let f and g be two maps from a set E into a set F such that f(x)≠g(x) for every x in E. Sahili has shown that, if min{|f^<-1>(z)|,|g^<-1>(z)|}≤n for each z∈F, then E can be partitioned into at most 2n+1 sets E_1,…,E_<2n+1> such that f(E_i)∩g(E_i)=0 for each i=1,…,2n+1. He also asked if 2n+1 is the best possible bound. By using Sahili's formulation of the problem in terms of the chromatic number of line digraphs, we improve the upper bound from 2n+1 to O(log n). We also investigate extended version for more than two maps.
- 社団法人電子情報通信学会の論文
- 2006-09-01
著者
-
Shibata Yukio
Department Of Electronic Engineering Tohoku University
-
Shibata Yukio
Department Of Computer Science Gunma University
-
Shibata Yukio
Department Of Computer Science Faculty Of Engineering Gunma University
-
Kawai Hiroyuki
Department Of Computer Engineering Hakodate-nct
関連論文
- A Minimum Feedback Vertex Set in the Trivalent Cayley Graph
- Optimal Diagnosable Systems on Cayley Graphs
- Efficient Diagnosis Algorithms on Butterfly Networks under the Comparison Approach(Special Section of Selected Papers from the 14th Workshop on Circuits and Systems in Karuizawa)
- Analysis of Negative Resistance Based on Space-Charge-Layers Overlapping in Switching Diodes with Deep Impurity Levels
- Delayed Switching in Crystalline Si Diodes with Deep Impurity Levels
- Diagnosability of Networks Represented by the Cartesian Product (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)
- Graph Products Based on the Distance in Graphs (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)
- Heavily Te-Doped GaAs Layers by Plasma-Assisted Epitaxy
- Low Temperature Thermal Nitridation of GaAs Surfaces
- Schottky Contact Characterization of Sputter-Etched Surface of GaAs and Its Recovery by Annealing
- Adaptive Diagnosis of Variants of the Hypercube(Graphs and Networks)
- An Optimal Adaptive Diagnosis of Butterfly Networks
- Gallium Oxide Film by Anodic Oxidization of Gallium
- Gallium Oxide Thin Film by Reactive Vapour Deposition
- Bulk Limited Conduction in Metal-Insulator-Metal Systems
- Titanium Oxycarbide on TiC (100) Surface
- P-n Junction Capacitance Thermometers
- Generalized Expression for Small Signal Impedance of Solid State Single Injection Diodes Including Space Charge Effects
- The Thermally Stimulated Current of Evaporated Silicon Oxide Films
- Dichroic Dyes for Guest-Host Liquid-Crystal Cells
- Ultrasonic Generation by Ferromagnetic Resonace in Evaporated Ni-Fe Alloy Films.I
- The Chromatic Number and the Chromatic Index of de Bruijn and Kautz Digraphs
- Partitions, Functions and the Arc-Coloring of Digraphs(Graphs and Networks)
- Plasma-Assisted Deposition of GaAs Thin Films : III-3: III-V COMPOUND SOLAR CELLS
- Generalized Small Signal Admittances of Solid State Diodes
- Transient Response Simulation of Semiconductor Diodes with Deep Impurity Levels
- Dihedral butterfly digraph and its Cayley graph representation
- Multisource Broadcasting on de Bruijn and Kautz Digraphs Using Isomorphic Factorizations into Cycle-Rooted Trees
- Cayley Graph Representation and Graph Product Representation of Hypercubes
- An Algorithm for Multi-Source Broadcasting on Kautz Digraphs Using 2-Cycle Rooted Trees
- Diffusion Effect on Negative Resistance in Semiconductor Diodes with Deep Impurity Levels