Affordable Access

Publisher Website

TheP4-sparse Graph Sandwich Problem

Authors
Journal
Electronic Notes in Discrete Mathematics
1571-0653
Publisher
Elsevier
Publication Date
Volume
22
Identifiers
DOI: 10.1016/j.endm.2005.06.037
Keywords
  • Graph Sandwich Problems
  • Algorithms
  • Computational Complexity
Disciplines
  • Computer Science

Abstract

Abstract The P 4 -sparse Graph Sandwich Problem asks, given two graphs G 1 = ( V , E 1 ) and G 2 = ( V , E 2 ) , whether there exists a graph G = ( V , E ) such that E 1 ⊆ E ⊆ E 2 and G is P 4 -sparse. In this paper we present a polynomial-time algorithm for solving the Graph Sandwich Problem for P 4 -sparse graphs.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

The Graph Sandwich Problem for [formula omitted]-s...

on Discrete Mathematics Jan 01, 2009

On theP4-components of graphs

on Discrete Applied Mathematics Jan 01, 2000

On semi-P4-sparse graphs

on Discrete Mathematics Jan 01, 1997

On theP4-structure of Perfect Graphs. IV. Partner...

on Journal of Combinatorial Theor... Jan 01, 1990
More articles like this..