Layered graphs: a class that admits polynomial time solutions for some hard problems

Bhadrachalam Chitturi

The independent set on a graph $G=(V,E)$ is a subset of $V$ such that no two vertices in the subset have an edge between them. The MIS problem on $G$ seeks to identify an independe…