Let M = (m_{ij}) be a symmetric matrix of order n and let G be the graph with vertex set {1,…,n} such that distinct vertices i and j are adjacent if and only if m_{ij} ≠ 0. We introduce a dynamic programming algorithm that finds a diagonal matrix that is congruent to M. If G is given with a tree decomposition 𝒯 of width k, then this can be done in time O(k|𝒯| + k² n), where |𝒯| denotes the number of nodes in 𝒯.

Multi-clique-width is obtained by a simple modification in the definition of clique-width. It has the advantage of providing a natural extension of tree-width. Unlike clique-width, it does not explode exponentially compared to tree-width. Efficient algorithms based on multi-clique-width are still possible for interesting tasks like computing the independent set polynomial or testing c-colorability. In particular, c-colorability can be tested in time linear in n and singly exponential in c and the width k of a given multi-k-expression. For these tasks, the running time as a function of the multi-clique-width is the same as the running time of the fastest known algorithm as a function of the clique-width. This results in an exponential speed-up for some graphs, if the corresponding graph generating expressions are given. The reason is that the multi-clique-width is never bigger, but is exponentially smaller than the clique-width for many graphs. This gap shows up when the tree-width is basically equal to the multi-clique width as well as when the tree-width is not bounded by any function of the clique-width.

For more than 35 years, the fastest known method for integer multiplication has been the Schönhage–Strassen algorithm running in time $O(n\log n\log\log n)$. Under certain restrictive conditions, there is a corresponding $\Omega(n\log n)$ lower bound. All this time, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is $\Theta(n\log n)$. We take a major step towards closing the gap between the upper bound and the conjectured lower bound by presenting an algorithm running in time $n\log n\,2^{O(\log^*n)}$. The running time bound holds for multitape Turing machines. The same bound is valid for the size of Boolean circuits.

For more than 35 years, the fastest known method for integer multiplication has been the Schönhage-Strassen algorithm running in time O(n log n log log n). Under certain restrictive conditions there is a corresponding Ω(n log n) lower bound. The prevailing conjecture has always been that the complexity of an optimal algorithm is Θ(n log n). We present a major step towards closing the gap from above by presenting an algorithm running in time n log n, 2O(log* n).

Article Free Access Share on Approximating permanents of complex matrices Author: Martin Fürer Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA Department of Computer Science and Engineering, Pennsylvania State University, University Park, PAView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 667–669https://doi.org/10.1145/335305.335399Published:01 May 2000Publication History 2citation362DownloadsMetricsTotal Citations2Total Downloads362Last 12 Months22Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We define a powerful new approximation technique called semi-local optimization.It provides very natural heuristics that are distinctly more powerful than those based on local optimization.With an appropriate metric, semi-local optimization can still be viewed as a local optimization, but it has the advantage of making global changes to an approximate solution.Semi-local optimization generalizes recent heuristics of Halld6rsson for 3-Set Cover, Color Saving, and k-Set Cover.Greatly improved performance ratios of 4/3 for 3-Set Cover and 6/5 for Color Saving in graphs without independent sets of size 4 are obtained and shown to be the best possible with semi-local optimization.Also, based on the result for 3-Set Cover and a restricted greedy phase for big sets, we can improve the performance ratio for k-Set Cover to ~k -1/2.In Color Saving, when larger independent sets exist, we can improve the performance ratio to ~.

First, a simplified geometric proof is presented for the result of C. Lund and M. Yannakakis (1994) saying that for some /spl epsiv/>0 it is NP-hard to approximate the chromatic number of graphs with N vertices by a factor of N/sup /spl epsiv//. Then, more sophisticated techniques are employed to improve the exponent. A randomized twisting method allows us to completely pack a certain space with copies of a graph without much affecting the independence number. Together with the newest results of M. Bellare et al. (1995), on the number of amortized free bits, it is shown that for every /spl epsiv/>0 the chromatic number cannot be approximated by a factor of N/sup 1/5-/spl epsiv// unless NP=ZPP. Finally, we get polynomial lower bounds in terms of /spl chi/. Unless NP=ZPP, the performance ratio of every polynomial time algorithm approximating the chromatic number of /spl chi/-colorable graphs (i.e., the chromatic number is at most /spl chi/) is at least /spl chi//sup 1/5-o(1/) (where the o-notation is with respect to /spl chi/).

A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight, lines joining their incident vertices. Given an n-vertex embedded planar graph with $n \geq 3$, a straight-line embedding on a grid of size $( n - 2 ) \times ( n - 2 )$ can be computed deterministically in $O( \log n\log \log n )$ time with $n/\log n\log \log n$ processors. If randomization is used, the complexity is improved to $O( \log n )$ expected time with the same optimal linear work. These algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes of the shared memory and permits an arbitrary processor to succeed in case of a write conflict.

A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight lines joining their incident vertices.Given an n-vertex planar graph with n ~3, a straight-line embedding on a grid of size (n-2)X(n-2) can be computed deterministically in O(log n log log n) time with O(n log log n) work on a parallel random access machine.If randomization is used, the complexity is improved to O(log n) expected time with the same work bound.The parallel random access machine used by these algorithms allows concurrent reads and concurrent writes of the shared memory; in case of a write conflict, an arbitrary processor succeeds.sonably small grids are very useful in visualizing planar graphs on graphic screens and have wide applications in CAD/CAM and Computer Graphics [8], [27].Wagner [28], Fziry [9], and Stein [24] showed that every planar graph has a straight-line embedding.Since

It is shown that Omega (n) variables are needed for first-order logic with counting to identify graphs on n vertices. This settles a long-standing open problem. The lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that three variables suffice to identify all graphs of color class size 3, and two variables suffice to identify almost all graphs. The lower bound is optimal up to multiplication by a constant because n variables obviously suffice to identify graphs on n vertices.>

VLSI designs for Galois field multipliers, which are central in many encoding and decoding procedures for error-detecting and error-correcting codes, are presented. An AT/sup 2/-optimal Galois-field multiplier based on AT/sup 2/-optimal integer multipliers for a synchronous VLSI model is exhibited. Galois field multiplication is done in two steps. First two polynomials (of degree n-1) over Z/sub p/ are multiplied, and then the resulting polynomial is reduced modulo a fixed irreducible polynomial (of degree n). Multiplication of polynomials is done by discrete Fourier transform (DFT). For p=2, the procedure is more involved for Z/sub p/(x) than for Z(x). An extension to the case of variable p is included and some open problems are stated.>

Improving a result of Mehlhorn and Schmidt, a function f with deterministic communication complexity n2 is shown to have Las Vegas communication complexity Ο(n). This is the best possible, because the deterministic complexity cannot be more than the square of the Las Vegas communication complexity for any function.

A function f is defined, mapping graphs with n vertices onto graphs with vertex set {1,...,n} . f(X) is isomorphic to X and X is isomorphic to Y iff f(X) = f(Y). For each d, the restriction of f to graphs of valence d is computable in time O(nτ(d)) for a suitable integer τ(d).

Let k be a constant ≥ 2, and let us consider only deterministic k-tape Turing machines.