When dealing with special graph classes and algorithmic problems on them, a main source
is the classical book of Golumbic, Algorithmic Graph Theory and Perfect Graphs [454]. The …

In this paper we give, for all constantsk, l, explicit algorithms that, given a graphG=(V, E) with
a tree-decomposition ofGwith treewidth at mostl, decide whether the treewidth (or pathwidth) …

This paper gives an overview of several results and techniques for graphs algorithms that
compute the treewidth of a graph or that solve otherwise intractable problems when …

We use the notion of potential maximal clique to characterize the maximal cliques appearing
in minimal triangulations of a graph. We show that if these objects can be listed in …

We present a new approach for designing external graph algorithms and use it to design
simple, deterministic and randomized external algorithms for computing connected …

In this paper, we show that the treewidth and pathwidth of a permutation graph can be
computed in polynomial time. In fact we show that, for permutation graphs, the treewidth and …

A potential maximal clique of a graph is a vertex set that induces a maximal clique in some
minimal triangulation of that graph. It is known that if these objects can be listed in …

A graph G is K-chordal, if it does not contain chordless cycles of length larger than k. The
chordality lc of a graph G is the minimum k for which G is k-chordal. The degeneracy or the …

Consider a class of graphs G having a polynomial time algorithm computing the set of all
minimal separators for every graph in G. We show that there is a polynomial time algorithm …

In this paper we show that the treewidth of a circle graph can be computed in polynomial
time. A circle graph is a graph that is isomorphic to the intersection graph of a finite collection …