Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419769 | Discrete Applied Mathematics | 2013 | 13 Pages |
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
Maw-Shang Chang, Ling-Ju Hung, Peter Rossmanith,