๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs

โœ Scribed by H. Bodlaender; T. Kloks

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
560 KB
Volume
15
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 recognizing partial (k)-trees. In this paper we give a simple linear time algorithm that solves the problem when there are three colors. We do this by first giving a complete structural characterization of the class of partial two-trees. (C) 1993 Academic Press, Inc

๐Ÿ“œ SIMILAR VOLUMES

A Simple Linear Time Algorithm for Prope
A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs
โœ Xin He ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 219 KB

In this paper we introduce a new style of drawing a plane graph G, called proper ลฝ . box rectangular PBR drawing. It is defined to be a drawing of G such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal or a vertical line segment, and each face is dr

A linear time algorithm for edge colorin
A linear time algorithm for edge coloring of binomial trees
โœ M. Kubale; K. Piwakowski ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 448 KB

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(