Hardness of Approximating Independent Domination in Circle Graphs.

A graph G = (V,E) is called a circle graph if there is a one- to-one correspondence between vertices in V and a set C of chords in a circle such that two vertices in V are adjacent if and only if the corresponding chords in C intersect. A subset V′ of V is a dominating set of G if for all u ∈ V eith...

Full description

Bibliographic Details
Main Authors: Damian-Iordache, Mirela., Pemmaraju, Sriram V.
Format: Villanova Faculty Authorship
Published: 1999
Online Access:http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175680