Can I read An Efficient Algorithm for Solving the Homogeneous Set Sandwich Problem on EtoBox?

An Efficient Algorithm for Solving the Homogeneous Set Sandwich Problem by Shyue-Ming Tang; Fu-Long Yeh; Yue-Li Wang is a Computer Science article available to read on EtoBox.

What is An Efficient Algorithm for Solving the Homogeneous Set Sandwich Problem about?

A set H of vertices of graph G(V , E) is a homogeneous set if each vertex in V \ H is either adjacent to all vertices of H or to none of the vertices in H , where V and E are the vertex set and edge set, respectively, of graph The homogeneous set sandwich problem is to determine whether there exists a sandwich graph for the pair of graphs G and G t such that there is a homogeneous set in G s . In this paper, we shall propose an O(∆n 2 ) time algorithm for solving the homogeneous set sandwich problem, where ∆ is the maximum degree of G. Furthermore, a surprising result comes from the bias graph which is an auxiliary graph for reducing the homogeneous set sandwich problem to the problem of finding strongly connected components. Using the bias graph, we can easily find all homogeneous sets for a sandwich graph problem with the same time complexity, i.e., O(∆n 2 ).

Who reads An Efficient Algorithm for Solving the Homogeneous Set Sandwich Problem?

Author

Shyue-Ming Tang; Fu-Long Yeh; Yue-Li Wang

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0020-0190)

Published

2001

Language

EN

Field

Computer Science (Physical Sciences)