Article ID Journal Published Year Pages File Type
419769 Discrete Applied Mathematics 2013 13 Pages PDF
Abstract

Let GG denote a graph class. An undirected graph GG is called a probe GG graph if one can make GG a graph in GG by adding edges between vertices in some independent set of GG. By definition graph class GG is a subclass of probe GG graphs. A graph is distance hereditary if the distance between any two vertices remains the same in every connected induced subgraph. Bipartite distance-hereditary graphs are both bipartite and distance hereditary. In this paper we propose O(nm)O(nm)-time algorithms to recognize probe distance-hereditary graphs and probe bipartite distance-hereditary graphs where nn and mm are the numbers of vertices and edges of the input graph respectively.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,