ﻻ يوجد ملخص باللغة العربية
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. This algorithm leads to linear-time isomorphism algorithms for related graph classes, including Helly circular-arc graphs, Gamma-circular-arc graphs, proper circular-arc graphs and convex-round graphs.
We show that it is possible to use Bondy-Chvatal closure to design an FPT algorithm that decides whether or not it is possible to cover vertices of an input graph by at most k vertex disjoint paths in the complement of the input graph. More precisely
In a (parameterized) graph edge modification problem, we are given a graph $G$, an integer $k$ and a (usually well-structured) class of graphs $mathcal{G}$, and ask whether it is possible to transform $G$ into a graph $G in mathcal{G}$ by adding and/
We give a family of counter examples showing that the two sequences of polytopes $Phi_{n,n}$ and $Psi_{n,n}$ are different. These polytopes were defined recently by S. Friedland in an attempt at a polynomial time algorithm for graph isomorphism.
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular ar
Given two graphs $G_1$ and $G_2$ on $n$ vertices each, we define a graph $G$ on vertex set $V_1times V_2$ and the edge set as the union of edges of $G_1times bar{G_2}$, $bar{G_1}times G_2$, ${(v,u),(v,u))(|u,uin V_2}$ for each $vin V_1$, and ${((u,v)