✦ LIBER ✦

On Crossing Sets, Disjoint Sets, and Pagenumber

✍ Scribed by Farhad Shahrokhi; Weiping Shi

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 109 KB
Volume: 34
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1999.1049

No coin nor oath required. For personal study only.

✦ Synopsis

Let G s V, E be a t-partite graph with n vertices and m edges, where the Ž 2 1.5 . partite sets are given. We present an O n m time algorithm to construct drawings of G in the plane so that the size of the largest set of pairwise crossing Ž edges and, at the same time, the size of the largest set of disjoint pairwise ' . Ž . noncrossing edges are O tи m . As an application we embed G in a book of 2 1.5 ' Ž . Ž . O tи m pages, in O n m time, resolving an open question for the pagenumber problem. A similar result is obtained for the dual of the pagenumber or the queuenumber. Our algorithms are obtained by derandomizing a probabilistic proof.

📜 SIMILAR VOLUMES

Note on disjoint blocking sets in Galois

Note on disjoint blocking sets in Galois planes

✍ János Barát; Stefano Marcugini; Fernanda Pambianco; Tamás Szőnyi 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

## Abstract In this paper, we show that there are at least __cq__ disjoint blocking sets in PG(2,__q__), where __c__ ≈ 1/3. The result also extends to some non‐Desarguesian planes of order __q__. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 149–158, 2006

Almost Disjoint Families of Representing

Almost Disjoint Families of Representing Sets

✍ Kevin P. Balanda 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB

Overlarge sets of disjoint Steiner quadr

Overlarge sets of disjoint Steiner quadruple systems

✍ Luc Teirlinck 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

In this article, we construct overlarge sets of disjoint S(3, 4, 3 n -1) and overlarge sets of disjoint S(3, 4, 3 n + 1) for all n ≥ 2. Up to now, the only known infinite sequence of overlarge sets of disjoint S(3, 4, v) were the overlarge sets of disjoint S(3, 4, 2 n ) obtained from the oval conics

On balanced sets and cores

✍ Lloyd S. Shapley 📂 Article 📅 1967 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB

CORES L l o y d S . S h a p l e y ## T h e R a n d C o r p o r a t i o n \* \* \*

On feedback vertex sets and nonseparatin

On feedback vertex sets and nonseparating independent sets in cubic graphs

✍ Ewald Speckenmeyer 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 341 KB

Let G be an undirected connected graph with n nodes. A subset F of nodes of G is a feedback vertex set (fvs) if G -F is a forest and a subset J of nodes of G is a nonseparating independent set (nsis) if no two nodes of J are adjacent and G -J is connected. f(G), z ( G ) denote the cardinalities of a

Crossing unordered sets of rules in evol

Crossing unordered sets of rules in evolutionary fuzzy controllers

✍ Luis Magdalena 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 206 KB

In recent years the use of genetic or evolutionary techniques has produced interesting results in the automatic generation of knowledge bases for fuzzy logic controllers. Three different representations of the rule base have been considered: lists of rules, relational matrices, and decision tables.