Edge-Coloring Problems for Graphs
スポンサーリンク
概要
- 論文の詳細を見る
The edge-coloring problem is one of the fundamental problems on graphs, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey old and new results on the classical edge-coloring problem as well as the generalized edge-coloring problems, called the f -coloring and f g -coloring problems. In particular we especially review various upper bounds on the minimum number of colors required to edge-color graphs, and present efficient algorithms to edge-color graphs with a number of colors not exceeding the upper bounds.
- 東北大学の論文
著者
-
Nishizeki T
Tohoku Univ. Sendai Jpn
-
Nishizeki Takao
Tohoku Univ. Sendai‐shi Jpn
-
Nishizeki Takao
Graduate School Of Information Sciences Tohoku University
-
Nishizeki Takao
Graduate School Of Information Sciences
-
Nakano Shin-ichi
Graduate School of Information Sciences
-
Nakano S
Faculty Of Agriculture Ehime University
関連論文
- Abundance and composition of the summer phytoplankton community along a transect from the Barguzin River to the central basin of Lake Baikal
- Abundance and pigment type composition of picocyanobacteria in Barguzin Bay, Lake Baikal
- List Edge-Colorings of Series-Parallel Graphs
- Linear Algorithm for Finding List Edge-Colorings of Series-Parallel Graphs (Special Issue on Selected Papers from LA Symposium)
- Quantum Card Dealing
- Necessary and Sufficient Numbers of Cards for Sharing Secret Keys on Hierarchical Groups(Special Issue on Selected Papers from LA Symposium)
- Sufficient Condition and Algorithm for List Total Colorings of Series-Parallel Graphs(Discrete Mathematics and Its Applications)
- Algorithms for Drawing Plane Graphs(Foundations of Computer Science)
- 平面グラフの格子短形描画
- On the One-Way Algebraic Homomorphism (Special Section on Cryprography and Information Security)
- Cost Total Colorings of Trees(Foundations of Computer Science)
- Dominance of Microcystis with Special Reference to Carbon Availability in Lake Water
- Fatty acid composition as an indicator of physiological condition of the cyanobacterium Microcystis aeruginosa
- Effect of cyanobacterial blooms on thermal stratification
- LA-10 A Linear Algorithm for Rectangular Drawings of Planar Graphs
- LA-9 Rectangle-of-Influence Drawings of Four-Connected Plane Graphs
- Edge-Coloring Problems for Graphs
- Mining Communities on the Web Using a Max-Flow and a Site-Oriented Framework(Data Mining)
- Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size(Graph Algorithms,Foundations of Computer Science)
- Algorithms for Multicolorings of Partial ★-Trees (Special Issue on Selected Papers from LA Symposium)
- Nutrient limitation of the primary production of phytoplankton in Lake Baikal
- Convex Drawings of Internally Triconnected Plane Graphs on O(n^2) Grids
- Best Security Index for Digital Fingerprinting(Information Hiding, Cryptography and Information Security)
- New Security Index for Digital Fingerprinting and Its Bounds
- Efficient Compression of Web Graphs
- Generalized Edge-Rankings of Trees
- Bipartition of Biconnected Graphs
- One-Way Functions over Finite Near-Rings
- Vertical planktonic structure in the central basin of Lake Baikal in summer 1999, with special reference to the microbial food web
- An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem