𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A linear time algorithm for edge coloring of binomial trees

✍ Scribed by M. Kubale; K. Piwakowski

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
448 KB
Volume
150
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of efficient coloring of the edges of a so-called binomial tree T, i.e. acyclic graph containing two kinds of edges: those which must have a single color and those which are to be colored with L consecutive colors, where L is an arbitrary integer greater than 1. We give an O(n) time algorithm for optimal coloring of such a tree, where n is the number of vertices of T. Also, we give simple bounds on the chromatic index of T and a division of all binomial trees into two classes depending on their chromaticity.

πŸ“œ SIMILAR VOLUMES

A Linear Algorithm for Edge-Coloring Ser
A Linear Algorithm for Edge-Coloring Series–Parallel Multigraphs
✍ Xiao Zhou; Hitoshi Suzuki; Takao Nishizeki πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 313 KB

Many combinatorial problems can be efficiently solved for series᎐parallel multigraphs. However, the edge-coloring problem of finding the minimum number of colors required for edge-coloring given graphs is one of a few well-known combinatorial problems for which no efficient algorithms have been obta

A Linear Time Algorithm for Finding ak-T
A Linear Time Algorithm for Finding ak-Tree Core
✍ Akiyoshi Shioura; Takeaki Uno πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 173 KB

Given a tree containing n vertices, consider the sum of the distance between all Ε½ . vertices and a k-leaf subtree subtree which contains exactly k leaves . A k-tree core is a k-leaf subtree which minimizes the sum of the distances. In this paper, we propose a linear time algorithm for finding a k-t

A linear-time algorithm for broadcast do
A linear-time algorithm for broadcast domination in a tree
✍ John Dabney; Brian C. Dean; Stephen T. Hedetniemi πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 268 KB

## Abstract The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power __p__ at vertex __v__ is capable of dominating (broadcasting to) all vertices within distance __p__ from __v__. Our goal is to assign a broadcast power __f__(__v

A Simple Linear Time Algorithm for Trian
A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
✍ H. Bodlaender; T. Kloks πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 560 KB

In this paper we consider the problem of determining whether a given colored graph can be triangulated, such that no edges between vertices of the same color are added. This problem originated from the perfect phylogeny problem from molecular biology and is strongly related with the problem of recog

A linear-time algorithm for connectedr-d
A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
✍ BrandstοΏ½dt, Andreas; Dragan, Feodor F. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 83 KB πŸ‘ 1 views

A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree