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 …

Closeness centrality is an important concept in social network analysis. In a graph
representing a social network, closeness centrality measures how close a vertex is to all …

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 …

Any given graph can be embedded in a chordal graph by adding edges, and the resulting
chordal graph is called a triangulation of the input graph. In this paper we study minimal …

Treewidth is a graph parameter with several interesting theoretical and practical
applications. This survey reviews algorithmic results on determining the treewidth of a given …

Abstract The Independent Set problem is NP-hard in general, however polynomial time
algorithms exist for the problem on various specific graph classes. Over the last couple of …

We obtain an algorithmic metatheorem for the following optimization problem. Let φ be a
counting monadic second order logic (CMSO) formula and t≧0 be an integer. For a given …

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 …

The Minimum Fill-in problem is used to decide if a graph can be triangulated by adding at
most k edges. In 1994, Kaplan, Shamir, and Tarjan showed that the problem is solvable in …

Listing all Minimal Separators of a Graph Page 1 LISTING ALL MINIMAL SEPARATORS OF A
GRAPH ∗ T. KLOKS† AND D. KRATSCH‡ SIAM J. COMPUT. c 1998 Society for Industrial and …