The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs

Details The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs

2008-11-25

arxiv.org/abs/0811.4007v1

Computer Science

Discrete Mathematics

15 pages, 1 figure

Scientific paper

In this paper we introduce the 'simultaneous membership problem', defined for any graph class C characterized in terms of representations, e.g. any class of intersection graphs. Two graphs G_1 and G_2, sharing some vertices X (and the corresponding induced edges), are said to be 'simultaneous members' of graph class C, if there exist representations R_1 and R_2 of G_1 and G_2 that are "consistent" on X. Equivalently (for the classes C that we consider) there exist edges E' between G_1-X and G_2-X such that G_1 \cup G_2 \cup E' belongs to class C. Simultaneous membership problems have application in any situation where it is desirable to consistently represent two related graphs, for example: interval graphs capturing overlaps of DNA fragments of two similar organisms; or graphs connected in time, where one is an updated version of the other. Simultaneous membership problems are related to simultaneous planar embeddings, graph sandwich problems and probe graph recognition problems. In this paper we give efficient algorithms for the simultaneous membership problem on chordal, comparability and permutation graphs. These results imply that graph sandwich problems for the above classes are tractable for an interesting special case: when the set of optional edges form a complete bipartite graph. Our results complement the recent polynomial time recognition algorithms for probe chordal, comparability, and permutation graphs, where the set of optional edges form a clique.

Affiliated with

Also associated with

No associations

Rating

The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-303823