| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4648592 | Discrete Mathematics | 2009 | 10 Pages |
Abstract
The P4P4-sparse Graph Sandwich Problem asks, given two graphs G1=(V,E1)G1=(V,E1) and G2=(V,E2)G2=(V,E2), whether there exists a graph G=(V,E)G=(V,E) such that E1⊆E⊆E2E1⊆E⊆E2 and GG is P4P4-sparse. In this paper we present a polynomial-time algorithm for solving the Graph Sandwich Problem for P4P4-sparse graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Simone Dantas, Sulamita Klein, Célia P. de Mello, Aurora Morgana,