A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems

Abstract. A subset A of the vertices of a graph G is an asteroidal set if for each vertex a ∈ A a connected component of G-N[a] exists containing A\backslash{a} . An asteroidal set of cardinality three is called asteriodal triple and graphs without an asteriodal triple are called AT-free . The maximum cardinality of an asteroidal set of G , denoted by \an(G) , is said to be the asteriodal number of G . We present a scheme for designing algorithms for triangulation problems on graphs. As a consequence, we obtain algorithms to compute graph parameters such as treewidth, minimum fill-in and vertex ranking number. The running time of these algorithms is a polynomial (of degree asteriodal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph.     

Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs

Abstract. We present an algorithm that constructively produces a solution to the k -DOMINATING SET problem for planar graphs in time O(c^ \sqrt k n) , where c=4^ 6\sqrt 34 . To obtain this result, we show that the treewidth of a planar graph with domination number γ (G) is O(\sqrt \rule 0pt 4pt \smash γ (G) ) , and that such a tree decomposition can be found in O(\sqrt \rule 0pt 4pt \smash γ (G) n) time. The same technique can be used to show that the k -FACE COVER problem (find a size k set of faces that cover all vertices of a given plane graph) can be solved in O(c ₁ ^ \sqrt k n) time, where c ₁ =3^ 36\sqrt 34 and k is the size of the face cover set. Similar results can be obtained in the planar case for some variants of k -DOMINATING SET, e.g., k -INDEPENDENT DOMINATING SET and k -WEIGHTED DOMINATING SET.     

NMR studies of Ca2+ binding to the regulatory domains of cardiac and E41A skeletal muscle troponin C reveal the importance of site I to energetics of the induced structural changes

Ca2+ binding to the N-domain of skeletal muscle troponin C (sNTnC) induces an "opening" of the structure [Gagné, S. M., et al. (1995) Nat. Struct. Biol. 2, 784-789], which is typical of Ca2+-regulatory proteins. However, the recent structures of the E41A mutant of skeletal troponin C (E41A sNTnC) [Gagné, S. M., et al. (1997) Biochemistry 36, 4386-4392] and of cardiac muscle troponin C (cNTnC) [Sia, S. K., et al. (1997) J. Biol. Chem. 272, 18216-18221] reveal that both of these proteins remain essentially in the "closed" conformation in their Ca2+-saturated states. Both of these proteins are modified in Ca2+-binding site I, albeit differently, suggesting a critical role for this region in the coupling of Ca2+ binding to the induced structural change. To understand the mechanism and the energetics involved in the Ca2+-induced structural transition, Ca2+ binding to E41A sNTnC and to cNTnC have been investigated by using one-dimensional 1H and two-dimensional {1H,15N}-HSQC NMR spectroscopy. Monitoring the chemical shift changes during Ca2+ titration of E41A sNTnC permits us to assign the order of stepwise binding as site II followed by site I and reveals that the mutation reduced the Ca2+ binding affinity of the site I by approximately 100-fold [from KD2 = 16 microM [sNTnC; Li, M. X., et al. (1995) Biochemistry 34, 8330-8340] to 1.3 mM (E41A sNTnC)] and of the site II by approximately 10-fold [from KD1 = 1.7 microM (sNTnC) to 15 microM (E41A sNTnC)]. Ca2+ titration of cNTnC confirms that cNTnC binds only one Ca2+ with a determined dissociation constant KD of 2.6 microM. The Ca2+-induced chemical shift changes occur over the entire sequence in cNTnC, suggesting that the defunct site I is perturbed when site II binds Ca2+. These measurements allow us to dissect the mechanism and energetics of the Ca2+-induced structural changes.     

A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems

A subset A of the vertices of a graph G is an asteroidal set if for each vertex a ∈ A a connected component of G-N[a] exists containing A\backslash{a} . An asteroidal set of cardinality three is called asteriodal triple and graphs without an asteriodal triple are called AT-free . The maximum cardinality of an asteroidal set of G , denoted by \an(G) , is said to be the asteriodal number of G . We present a scheme for designing algorithms for triangulation problems on graphs. As a consequence, we obtain algorithms to compute graph parameters such as treewidth, minimum fill-in and vertex ranking number. The running time of these algorithms is a polynomial (of degree asteriodal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph.