𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On ordered graphs and graph orderings

✍ Scribed by Jaroslav Nešetřil

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
290 KB
Volume
51
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A note on graphs and sphere orders
A note on graphs and sphere orders
✍ Edward R. Scheinerman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract A partially ordered set __P__ is called a __k‐sphere order__ if one can assign to each element a ∈ __P__ a ball __B__~__a__~ in __R^k^__ so that __a__ < __b__ iff __B__~__a__~ ⊂ __B__~__b__~. To a graph __G__ = (__V,E__) associate a poset __P__(__G__) whose elements are the vertices and

Sharp bounds on the order, size, and sta
Sharp bounds on the order, size, and stability number of graphs
✍ Pierre Hansen; Maolin Zheng 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB

## Abstract We consider graphs __G = (V,E)__ with order ρ = |__V__|, size __e__ = |__E__|, and stability number β~0~. We collect or determine upper and lower bounds on each of these parameters expressed as functions of the two others. We prove that all these bounds are sharp. © __1993 by John Wiley

On approximability of linear ordering an
On approximability of linear ordering and related NP-optimization problems on graphs
✍ Sounaka Mishra; Kripasindhu Sikdar 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 337 KB

We investigate the approximability of minimum and maximum linear ordering problems (MIN-LOP and MAX-LOP) and related feedback set problems such as maximum weight acyclic subdiagraph (MAX-W-SUBDAG), minimum weight feedback arc/vertex set (MIN-W-FAS/ MIN-W-FVS) and a generalization of the latter calle