In all-optical networks that use WDM technology it is often the case that several communication requests have to be blocked, due to bandwidth and technology limitations. Minimizing request blocking is therefore an important task calling for algorithmic techniques for efficient routing and wavelength assignment. Here we study the problem for rings under both the undirected and the directed settings, corresponding to symmetric and one-way communication respectively. The problem in graph-theoretic terms can be formulated as the maximum routing and path coloring problem. We present a chain-and-matching technique for routing requests and coloring the corresponding paths which gives constant approximations for both the undirected and the directed cases. For the undirected problem we obtain a 2/3-approximation algorithm; this corresponds to a considerable increase in the number of satisfied requests compared to the best known algorithm so far, due to Wan and Liu (1998), that achieves a 1 - 1/e ratio using iteratively a maximum edge-disjoint paths algorithm. For the directed case, we also introduce a balanced matching method which, combined with the chain-and-matching technique, gives a 7/11-approximation algorithm. This algorithm also improves upon the (1 $1/e)-approximation algorithm that can be obtained by extending the iterative method of Wan and Liu.

A family of many-valued modal logics which correspond to possible-worlds models with many-valued accessibility relations, has been recently proposed by M. Fitting [7, 8]. Non-monotonic extensions of these logics are introduced with a fixpoint construction à la McDermott & Doyle and employ sequential belief sets as epistemic states [9]. In this paper we take a logical investigation of many-valued modal non-monotonic reasoning in Fitting's formal framework. We examine the notion of MV-stable sets which emerges as a sequential many-valued analog of Stalnaker-Moore stable sets and prove that several attractive epistemic properties are essentially retained in the many-valued setting, esp. when focusing on a syntactically simple epistemic fragment of MV-stable sets. We show that MV-stable sets are always closed under S4 consequence and identify three sufficient conditions for capturing axioms of negative introspection. Also, the relation of MV-stable sets to many-valued analogs of classical S5 models and to many-valued extensions of universal models is discussed. Finally, we pay special attention to the subclass of logics built on linear Heyting algebras and show that inside this subclass, the situation is very similar - in many respects - to the machinery devised by W. Marek, G. Schwarz and M. Truszczyński. In particular, the normal fragments of the two important classical ranges of modal non-monotonic logics remain intact: many-valued autoepistemic logic is captured by any non-monotonic logic in K5 – KD45 and many-valued reflexive autoepistemic logic corresponds to KTw5 – Sw5.