✦ LIBER ✦

Well covered simplicial, chordal, and circular arc graphs

✍ Scribed by Prisner, Erich; Topp, Jerzy; Vestergaard, Preben Dahl

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 427 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199602)21:2<113::aid-jgt1>3.0.co;2-u

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper, we,characterize well covered simplicial, chordal and circular arc graphs.

📜 SIMILAR VOLUMES

Subdivisions, parity and well-covered gr

Subdivisions, parity and well-covered graphs

✍ Caro, Yair 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 1 views

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm

ModelingK-coteries by well-covered graph

ModelingK-coteries by well-covered graphs

✍ Yamashita, Masafumi; Kameda, Tsunehiko (Tiko) 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 1 views

The concept of k-coterie is useful for achieving k-mutual exclusion in distributed systems. A graph is said to be well covered if any of its maximal independent sets is also maximum. We first show that a graph G is well covered with independence number k if and only if G represents the incidence rel

Tracking the P-NP boundary for well-cove

Tracking the P-NP boundary for well-covered graphs

✍ Sankaranarayana, Ramesh S. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB 👁 1 views

Certain fundamental graph problems like recognition, dominating set, Hamiltonian cycle and path, and clique partition, which are hard for well-covered graphs in general, can be solved efficiently for very well covered graphs. We address the question of how far the class of very well covered graphs c

Maximum independent sets of circular-arc

Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs

✍ Zheng, S. Q. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 421 KB 👁 1 views

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G , our algorithm computes a maximum independent set of G in O ( n ) space and O ( n ) or O(n log n ) time, depending on whether the

A characterization of Zm-well-covered gr

A characterization of Zm-well-covered graphs of girth 6 or more

✍ Caro, Y.; Hartnell, B. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

The class of Z m -well-covered graphs, those in which the cardinality of every maximal independent subset of vertices is congruent to the same number modulo m, contains the well-covered graphs as well as parity graphs. Here we consider such graphs, where there is no small cycle present and obtain a

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 👁 2 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