๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On locally optimal independent sets and vertex covers

โœ Scribed by Gang Yu; Olivier Goldschmidt

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
665 KB
Volume
43
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper, we introduce a new notion of local optimality and demonstrate its application to the problem of finding optimal independent sets and vertex covers in k-claw free graphs. The maximum independent set problem in k-claw free graphs has interesting applications in the design of electronic testing fixtures for printed circuit boards [ 131. For this problem, our concept of local optimality enabled us to devise an efficient heuristic algorithm which outperforms the currently best approximation algorithm by nearly a factor of two in terms of worst case bound. We believe that the idea of local optimality suggested in this paper can also be applied to other combinatorial problems such as the clique problem, the dominating set problem and the graph coloring problem.

๐Ÿ“œ SIMILAR VOLUMES

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

On covering an independent set in a grid
On covering an independent set in a grid with a second independent set
โœ Rue, Rachel ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 1011 KB

We show that for every independent set 0 in an n x m grid, n, m > 1, there is a second independent set X with the property that every member of 0 is adjacent to a t least one member of X. The proof gives a construction for X. Equivalently, we show that for every maximal independent set in a grid, th

Primitivity and independent sets in dire
Primitivity and independent sets in direct products of vertex-transitive graphs
โœ Huajun Zhang ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 92 KB

We introduce the concept of the primitivity of independent set in vertex-transitive graphs, and investigate the relationship between the primitivity and the structure of maximum independent sets in direct products of vertex-transitive graphs. As a consequence of our main results, we positively solve

On longest cycles and strongly linking v
On longest cycles and strongly linking vertex sets
โœ Bert Fassbender ๐Ÿ“‚ Article ๐Ÿ“… 1989 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 245 KB ๐Ÿ‘ 1 views

Let G be a simple non-hamiltonian graph, let C be a longest cycle in G, and let p be a positive integer. By considering a special form of connectivity, we obtain a sufficient condition on degrees for the nonexistence of ( p -1)-path-connected components in G -C.

On the nonseparating independent set pro
On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
โœ Shuichi Ueno; Yoji Kajitani; Shin'ya Gotoh ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 350 KB

This paper shows that both the nonseparating independent set problem and feedback set problem can be solved in polynomial time for graphs with no vertex degree exceeding 3 by reducing the problems to the matroid parity problem.