✦ LIBER ✦

Minimum Fill-in on Circle and Circular-Arc Graphs

✍ Scribed by T Kloks; D Kratsch; C.K Wong

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 184 KB
Volume: 28
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1998.0936

No coin nor oath required. For personal study only.

✦ Synopsis

We present two algorithms solving the minimum fill-in problem on circle graphs Ž 3 . and on circular-arc graphs in time O n .

📜 SIMILAR VOLUMES

Polynomial time algorithms on circular-a

Polynomial time algorithms on circular-arc overlap graphs

✍ Toshinobu Kashiwabara; Sumio Masuda; Kazuo Nakajima; Toshio Fujisawa 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 417 KB

On the L(h, k)-labeling of co-comparabil

On the L(h, k)-labeling of co-comparability graphs and circular-arc graphs

✍ Tiziana Calamoneri; Saverio Caminiti; Rossella Petreschi; Stephan Olariu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

Efficient algorithms for centers and med

Efficient algorithms for centers and medians in interval and circular-arc graphs

✍ Sergei Bespamyatnikh; Binay Bhattacharya; Mark Keil; David Kirkpatrick; Michael 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 267 KB

## Abstract The __p__‐center problem is to locate __p__ facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The __p__‐median problem is to locate __p__ facilities on a network so as to minimize the average distance from a demand point to its c

On k-domination and minimum degree in gr

On k-domination and minimum degree in graphs

✍ Odile Favaron; Adriana Hansberg; Lutz Volkmann 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

## Abstract A subset __S__ of vertices of a graph __G__ is __k__‐dominating if every vertex not in __S__ has at least __k__ neighbors in __S__. The __k__‐domination number $\gamma\_k(G)$ is the minimum cardinality of a __k__‐dominating set of __G__. Different upper bounds on $\gamma\_{k}(G)$ are kn

Solving the all-pair shortest path query

Solving the all-pair shortest path query problem on interval and circular-arc graphs

✍ Chen, Danny Z.; Lee, D. T.; Sridhar, R.; Sekharan, Chandra N. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 3 views

In this paper, we study the following all-pair shortest path query problem: Given the interval model of an unweighted interval graph of n vertices, build a data structure such that each query on the shortest path (or its length) between any pair of vertices of the graph can be processed efficiently

On minimum degree in Hamiltonian path gr

On minimum degree in Hamiltonian path graphs

✍ George R. T. Hendry 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views