Wireless Mesh Network (WMN) is a promising model with benefits in coverage extension and throughput improvement. In WMN, multiple channels are available for improving system performance through concurrent transmission. For maximum utilization, per-node channel quality and inter-channel interference should be considered in multi-channel assignment. We propose a new multi-channel assignment method. First, we model the mesh network connectivity after a multi-graph which has multiple edges between two nodes. From this connectivity graph, we generate a multi-channel conflict graph, then we allocate multiple channels so that they do not overlap, using list coloring algorithm. We also propose a new sub-graph list coloring algorithm to enhance channel allocation performance. From computer simulations, we verify the performance of the algorithm.

In this paper, we present a clean and simple formulation of survey propagation (SP) for constraint-satisfaction problems as "probabilistic token passing". The result shows the importance of extending variable alphabets to their power sets in designing SP algorithms.

This paper addresses the issue of transmission scheduling in wireless ad hoc networks. We propose a Time Division Multiple Access (TDMA) scheduling scheme based on edge coloring and probabilistic assignment, called CP-TDMA. We categorize the conflicts suffered by wireless links into two types: explicit conflicts and implicit conflicts, and utilize two different strategies to deal with them. Explicit conflicts are avoided completely by a simple distributed edge-coloring algorithm µ-M, and implicit conflicts are minimized by applying probabilistic time slot assignments to links. We evaluate CP-TDMA analytically and numerically, and find that CP-TDMA, which requires only local information exhibits a better performance than previous work.

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring for given L. In this paper, we give a sufficient condition for a series-parallel graph to have a list total coloring, and we present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G and L satisfy the sufficient condition.

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 [8] 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 E1,..., E2n+1 such that f(Ei)∩ g(Ei)= 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.

The path coloring problem is to assign the minimum number of colors to a given set P of directed paths on a given symmetric digraph D so that no two paths sharing an arc have the same color. The problem has applications to efficient assignment of wavelengths to communications on WDM optical networks. In this paper, we show that the path coloring problem is NP-hard even if the underlying graph of D is restricted to a binary caterpillar. Moreover, we give a polynomial time algorithm which constructs, given a binary caterpillar G and a set P of directed paths on the symmetric digraph associated with G, a path coloring of P with at most colors, where L is the maximum number of paths sharing an edge. Furthermore, we show that no local greedy path coloring algorithm on caterpillars in general uses less than colors.

A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(m log d + (m/d) log (m/d) log d) algorithm by Makino-Takabatake-Fujishige and the O(m log m) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(m log d + (m/d) log (m/d)) time. This algorithm does not require elaborate data structures, which the best known O(m log d) algorithm due to Cole-Ost-Schirra depends on.

This paper proposes a channel allocation principle that prevents TCP throughput degradation in multihop transmissions in a mesh network based on the carrier sense multiple access with collision avoidance (CSMA/CA) MAC protocol. We first address the relationship between the network topology of wireless nodes and the TCP throughput degradation based on computer simulations. The channel allocation principle is discussed in terms of resolution into a coloring problem based on throughput degradation. The number of required channels for the proposed channel allocation principle is evaluated and it is shown that two channels are sufficient for more than 96% simulated multihop patterns. The proposed channel allocation principle is extendable to generic mesh networks. We also clarify the number of required channels for mesh networks. The simulation results show that three channels are sufficient for more than 98% patterns in the generic mesh networks when the number of nodes is less than 10.

H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are -colorable if and only if they are p-colorable (p 2), (2) -coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many -colorable but non-3-colorable planar graphs.

Recently, the mulitihop wireless network system attracts the interest of many people as a communication network system of the next generation. The multihop wireless network has unique features in which neither base stations nor wired backbone networks are required and a terminal can communicate with the other terminal beyond the transmission range by multihopping. In this network, a communication link between two terminals which can communicate directly is required a channel. Since cochannel interference may occur, we need to assign channels to communication links carefully. In this paper, we describe a channel assignment strategy which takes the degree of cochannel interference into consideration, and we evaluate an effectiveness of this strategy by computer simulations. We show that this strategy is more effective than a strategy which does not take the degree of cochannel interference into consideration. And we also consider a few channel assignment algorithms briefly.

A nearly equitable edge-coloring of a multigraph is a coloring such that edges incident to each vertex are colored equitably in number. This problem was solved in O(kn2) time, where n and k are the numbers of the edges and the colors, respectively. The running time was improved to be O(n2/k + n|V|) later. We present a more efficient algorithm for this problem that runs in O(n2/k) time.

A total coloring of a graph G is to color all vertices and edges of G so that no two adjacent or incident elements receive the same color. Let C be a set of colors, and let ω be a cost function which assigns to each color c in C a real number ω(c) as a cost of c. A total coloring f of G is called an optimal total coloring if the sum of costs ω(f(x)) of colors f(x) assigned to all vertices and edges x is as small as possible. In this paper, we give an algorithm to find an optimal total coloring of any tree T in time O(nΔ3) where n is the number of vertices in T and Δ is the maximum degree of T.

Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). In this paper, we prove that any series-parallel simple graph G has an L-edge-coloring if |L(e)| max{3,d(v),d(w)} for each edge e = vw, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. Our proof yields a linear algorithm for finding an L-edge-coloring of series-parallel graphs.

Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any k-colorable graph with maximum degree Δ using (Δ1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using (n 1-3/(k+1)) colors. This improved Wigderson's algorithm, which uses O(n1-1/(k-1)) colors, containing as a subroutine an algorithm using (Δ+1) colors for graphs with maximum degree Δ. It is easy to imagine that an algorithm which uses less colors in terms of Δ leads to an algorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses (Δ 1-x/k) colors for 2

Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). It is known that any series-parallel simple graph G has an L-edge-coloring if either (i) |L(e)| max{4,d(v),d(w)} for each edge e=vw or (ii) the maximum degree of G is at most three and |L(e)| 3 for each edge e, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. In this paper we give a linear-time algorithm for finding such an L-edge-coloring of a series-parallel graph G.

Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.

There are several kinds of coloring of digraphs, such as vertex-coloring and arc-coloring. We call an arc-coloring of a digraph G the first type if it is an assignment of colors to the arc set of G in which no two consecutive arcs have the same color. In some researches, the arc-coloring of first type has been associated with the minimum number of the vertex-coloring called chromatic number. Considering the class of line digraphs, an arc-coloring of a digraph G of the first type is equivalent to the vertex-coloring of its line digraph L(G). In this paper, we study the arc-coloring of the first type and the vertex-coloring of line digraphs. We give the upper bound of the chromatic number of L(G) by the chromatic number of a digraph G which admits loops. It is also shown that there exists quite a small integer k so that the iterated line digraph Lk(G) is 3-vertex-colorable. As a consequence, we derive the chromatic number of de Bruijn and Kautz digraphs.

A kind of online edge-coloring problems on bipartite graphs is considered. The input is a graph (typically with no edges) and a sequence of operations (edge addition and edge deletion) under the restriction that at any time the graph is bipartite and degree-bounded by k, where k is a prescribed integer. At the time of edge addition, the added edge can be irrevocably assigned a color or be left uncolored. No other coloring or color alteration is allowed. The problem is to assign colors as many times as possible using k colors. Two algorithms are presented: one with competitiveness coefficient 1/4 against oblivious adversaries, and one with competitiveness coefficient between 1/4 and 1/2 with the cost of requiring more random bits than the former algorithm, also against oblivious adversaries.

Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.

An advanced spare-connection scheme for K-out-of-N redundancy is proposed for constructing fault-tolerant ring- or toroidal mesh-connected processing-node arrays able to enhance emulation of binary hypercubes by using bypass networks. With this scheme, a component redundancy configuration for a base array with a fixed number of primary nodes, such as that for 8-node ring or 32-node toroidal mesh, can be constructed by using bypass links with a segmented bus structure to selectively connect the primary nodes to a spare node in parallel. These bypass links are allocated to the primary nodes by graph-node coloring with a minimum inter-node distance of three in order to use the bypass links as the hypercube connections as well as to attain strong fault tolerance for reconfiguring the base array with the primary network topology. An extended redundancy configuration for a large fault-tolerant array can be constructed by connecting the component configurations by using external switches of a hub type provided at the bus nodes of the bypass links. This configuration has a network topology of the parallel star-connections of sub-hypercubes whose diameter is smaller than that of the regular hypercube.