Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

The Maximum Independent Set Problem For Cubic Planar Graphs

IP.com Disclosure Number: IPCOM000148948D
Original Publication Date: 1985-Aug-31
Included in the Prior Art Database: 2007-Mar-30
Document File: 7 page(s) / 440K

Publishing Venue

Software Patent Institute

Related People

Burns, James E.: AUTHOR [+2]

Abstract

by James E. Bum Computer Science Department Indiana University Bloomington, IN 47405 by TECHJSlICAL REPORT NO. 177 The Maximum Independent Set Problem For Cubic Planar Graphs James E, Burns August, 1985 THE MAXIMUM INDEPENDENT SET PROBLEM FOR CUBIC PLANAR GRAPHS James E. Burns June 1985 A maximum independent set of a graph is a set of verticm with maximum cardinal- ity such that no pair of vertices is connected by an edge. Choukhmane and b c o have presented a polynomial time approximation algorithm for the maximum inde- pendent set problem in cubic planar graphs. If M ia taken as the ratio of the sise of the independent set produced by their algorithm to the siee of a mdmum inde- pendent set of the input graph, then they show that their algorithm gives M 2 617 for any cubic planar graph and M 2 7/8 for a triangle-free cubic planar graph. We show that their algorithm gives M 2 7/8 for all cubic planar graphs. 1. INTRODUCTION The maximum independent set problem, defined formally in the next section, is a problem of wide interest. Unfortunately, it is known to be an NP-complete problem, so there is little hope for an algorithm which can compute an exact solution in polynomial time. (For a comprehensive treatment of NP-complete problems, see Garey and Johnsoni7].) It is therefore useful to consider solutions which are approximate, but can be computed efficiently.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 24% of the total text.

Page 1 of 7

The Maximum Independent Set Problem For Cubic Planar Graphs

        by
James E. Bum Computer Science Department Indiana University Bloomington, IN 47405

TECHJSlICAL REPORT NO. 177

The Maximum Independent Set Problem For Cubic Planar Graphs

by

James E, Burns August, 1985

[This page contains 1 picture or other non-text object]

Page 2 of 7

THE MAXIMUM INDEPENDENT SET PROBLEM FOR CUBIC PLANAR GRAPHS

James E. Burns

June 1985

ABSTRACT'

A maximum independent set of a graph is a set of verticm with maximum cardinal- ity such that no pair of vertices is connected by an edge. Choukhmane and b c o have presented a polynomial time approximation algorithm for the maximum inde- pendent set problem in cubic planar graphs. If M ia taken as the ratio of the sise of the independent set produced by their algorithm to the siee of a mdmum inde- pendent set of the input graph, then they show that their algorithm gives M 2 617 for any cubic planar graph and M 2 7/8 for a triangle-free cubic planar graph. We show that their algorithm gives M 2 7/8 for all cubic planar graphs.

1. INTRODUCTION

   The maximum independent set problem, defined formally in the next section, is a problem of wide interest. Unfortunately, it is known to be an NP-complete problem, so there is little hope for an algorithm which can compute an exact solution in polynomial time. (For a comprehensive treatment of NP-complete problems, see Garey and Johnsoni7].) It is therefore useful to consider solutions which are approximate, but can be computed efficiently.

For any algorithm W which produces an independent set I for some input graph

G, let Mw(G)

         be the ratio of the sire of I to the sise of a maximum independent set of G. For any clasa of graph 5, let Adw($) be! the minimum value of Mw(@) over all G E 5. We define QP = {planar graphs), = (cubic planar graphs), and $3TFP = {cubic triangle-free planar graphs). Lipton and %&rjan[lO]
give an

O(n log n) time algorithm, L, which is shown to give an approximation euch that

M'(gp) > (1 - O ( l / 4 i j ) , where n t the number of verticea in the input graph. Unfortunately, aa &own by Chiba et d[2], n must be rather large before

ML(gP)

  > 1/2. Chiba et d then describe an algorithm, C, which executes in Author's addresses: J.E. Burns, Computer Science Department, 101 Lindley

Hall, Indiana University, Bloomington, Indiana 47405.

[This page contains 1 picture or other non-text object]

Page 3 of 7

Barns The Maximum Independent Set Problem tot Cnbk Ptaaar Graphs

time O(nlogn) and show M~(fip)

                  > 1/2. B&er[l] improve thia result by giving a family of algorithms, Bd, for the maximum independent set problem such that

MBd(gP)

    > d/(d + I), and which execute in time O(sddn). Note that Baker's algorithms are linear for any fixed d.

   Choukhmane and Franco[3] describe a polynomial algorithm, A, for the max- imum independent set and show that MA(&P) 1 6/...