Andreas Brandstädt

collaborators

2 papers

cs.DM2011★ 8 cited

Dominating Induced Matchings for P7-Free Graphs in Linear Time

Andreas Brandstadt, Raffaele Mosca

Let $G$ be a finite undirected graph with edge set $E$ . An edge set $E^{'} \subseteq E$ is an {\em induced matching} in $G$ if the pairwise distance of the edges of $E^{'}$ in $G$ is at…

cs.DM2011

Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences

Andreas Brandstädt, Vassilis Giakoumakis

Clique separator decomposition introduced by Tarjan and Whitesides is one of the most important graph decompositions. A graph is an {\em atom} if it has no clique separator. A {\em…