Affordable Access

Publisher Website

Homogeneously orderable graphs

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
172
Identifiers
DOI: 10.1016/s0304-3975(96)00091-6
Disciplines
  • Computer Science

Abstract

Abstract In this paper we introduce homogeneously orderable graphs which are a common generalization of distance-hereditary graphs, dually chordal graphs and homogeneous graphs. We present a characterization of the new class in terms of a tree structure of the closed neighborhoods of homogeneous sets in 2-graphs which is closely related to the defining elimination ordering. Moreover, we characterize the hereditary homogeneously orderable graphs by forbidden induced subgraphs as the house-hole-domino-sun-free graphs. The local structure of homogeneously orderable graphs implies a simple polynomial-time recognition algorithm for these graphs. Finally, we give a polynomial-time solution for the Steiner tree problem on homogeneously orderable graphs which extends the efficient solutions of that problem on distance-hereditary graphs, dually chordal graphs and homogeneous 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

On BF-orderable graphs

on Discrete Applied Mathematics Jan 01, 1986

A note on perfectly orderable graphs

on Discrete Applied Mathematics Jan 01, 1996

Perfectly orderable graphs are quasi-parity graphs...

on Discrete Mathematics Jan 01, 1988
More articles like this..