#### Figures from this paper

#### One Citation

On the tractability of the maximum independent set problem

- Computer Science
- ArXiv
- 2019

This paper outlines the existence of an exact polynomial-time algorithm for the maximum independent set problem in graph theory in pseudo-code style, and proves its exactness and efficiency by analysis. Expand

#### References

SHOWING 1-10 OF 168 REFERENCES

Independent sets in (P6, diamond)-free graphs

- Mathematics, Computer Science
- Discret. Math. Theor. Comput. Sci.
- 2009

We prove that on ( P 6 ,diamond)-free graphs the Maximum Weight
Independent Set problem and the Minimum Weight Independent
Dominating Set problem can be solved in polynomial time.

On alpha-redundant vertices in P5-free graphs

- Mathematics, Computer Science
- Inf. Process. Lett.
- 2002

Abstract We prove that Maximum Stable Set can be solved in polynomial time on two new subclasses of P5-free graphs, extending some known polynomially solvable cases.

The Maximum Independent Set Problem and Augmenting Graphs

- Computer Science
- 2005

The method of augmenting graphs is reviewed, which is a general approach to solve the maximum independent set problem, and several new contributions to the topic are proposed. Expand

Augmenting graphs for independent sets

- Mathematics, Computer Science
- Discret. Appl. Math.
- 2004

This paper considers a general approach to solve the maximum independent set problem based on finding augmenting graphs, and describes a new one that generalizes two previously known algorithms. Expand

A Unified Approach to Domination Problems on Interval Graphs

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1988

Une propriete tres simple des graphes intervalle est utilisee dans la realisation d'algorithmes a temps lineaire, developpes pour la resolution de differents problemes de domination

Computing independent sets in graphs with large girth

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1992

It is shown that the well-known independent set problem remains NP-complete even when restricted to graphs which contain no cycles of length less than cnk where n is the number of vertices in the… Expand

Stability number in subclasses of P5-free graphs

- Mathematics
- 2004

Two new hereditary classes of P5-free graphs where the stability number can be found in polynomial time are proposed. They generalize several known results.

Stability number in subclasses of P5-free graphs

- 2004

Two new hereditary classes of P5-free graphs where the stability number can be found in polynomial time are proposed. They generalize several known results.

Independent Set in P5-Free Graphs in Polynomial Time

- Mathematics, Computer Science
- SODA
- 2014

This paper gives the first polynomial time algorithm for Independent Set on P5-free graphs, and this algorithm also works for the Weighted Independent Set problem. Expand

A lower bound on the independence number of a graph

- Computer Science, Mathematics
- Discret. Math.
- 1998

Abstract A new lower bound on the independence number of a graph is established and an accompanying efficient algorithm constructing an independent vertex set the cardinality of which is at least… Expand