Search

Abstract: Došlić and Måløy (2010) obtained the extremal 6-cactus chains with respect to the number of matchings and of independent sets. Motivated by the prior paper, in this paper we give recurrences for matching polynomials of ortho-chains and meta-chains, and show that they are the -cactus chains with the most matchings. [Copyright &y& Elsevier]

Abstract: The δ-annulus of a polygon P is the closed region containing all points in the plane at distance at most δ from the boundary of P. An inner (resp., outer) δ-offset polygon is the polygon defined by the inner (resp., outer) boundary of its δ-annulus. In this paper we address three major problems of covering a given point set S by an offset version or a polygonal annulus of a polygon P. First, the Maximum Cover objective is, given a value of δ, to cover as many points from S as possible by the δ-offset (or by the δ-annulus) of P, allowing translation and rotation. Second, the Containment problem is to minimize the value of δ such that there is a rigid transformation of the δ-offset (or the δ-annulus) of P that covers all points from S. Third, in the Partial Containment problem we seek the minimum offset of P covering points. These problems arise in many applications where one needs to match a given polygonal figure (a known model) to a set of points (usually, obtained measures). We address several variants of these problems, including convex and simple polygons, as well as polygons with holes and sets of polygons, and obtain algorithms with low-degree polynomial running times in all cases. [Copyright &y& Elsevier]

Abstract: In Suzuki (1998) [7] Suzuki gave a classification of association schemes with multiple Q-polynomial structures, allowing for one exceptional case which has five classes. In this paper, we rule out the existence of this case. Hence Suzukiʼs theorem mirrors exactly the well-known counterpart for association schemes with multiple P-polynomial structures, a result due to Eiichi Bannai and Etsuko Bannai in 1980. [Copyright &y& Elsevier]

Abstract: This paper introduces the notions of approximate and optimal approximate zero polynomial of a polynomial matrix by deploying recent results on the approximate GCD of a set of polynomials Karcaniaset al. (2006) 1 and the exterior algebra Karcanias and Giannakopoulos (1984) 4 representation of polynomial matrices. The results provide a new definition for the “approximate”, or “almost” zeros of polynomial matrices and provide the means for computing the distance from non-coprimeness of a polynomial matrix. The computational framework is expressed as a distance problem in a projective space. The general framework defined for polynomial matrices provides a new characterization of approximate zeros and decoupling zeros Karcanias et al. (1983) 2 and Karcanias and Giannakopoulos (1984) 4 of linear systems and a process leading to computation of their optimal versions. The use of restriction pencils provides the means for defining the distance of state feedback (output injection) orbits from uncontrollable (unobservable) families of systems, as well as the invariant versions of the “approximate decoupling polynomials”. The overall framework that is introduced provides the means for introducing measures for the distance of a system from different families of uncontrollable, or unobservable systems, which may be feedback dependent, or feedback invariant as well as the notion of “approximate decoupling polynomials”. [Copyright &y& Elsevier]

Abstract: Let be positive integers. A -edge-colored graph is -e.c. or -existentially closed if for any disjoint sets of vertices with , there is a vertex not in such that all edges from this vertex to the set are colored by the -th color. In this paper, we give an explicit construction of a -e.c. graph of polynomial order. [Copyright &y& Elsevier]

Abstract: Crouzeix’s conjecture is that for any square matrix A and any polynomial p we havewhere is the field of values of A and denotes the spectral norm. In this paper, we show that the conjecture holds for the matrices of the formwhere and . [Copyright &y& Elsevier]

Abstract: Let G σ be an oriented graph obtained by assigning an orientation σ to the edge set of a simple undirected graph G such that G σ becomes a directed graph. Let S(G σ ) be the skew adjacency matrix of G σ . The skew energy of G σ is defined as the sum of the absolute values of all eigenvalues of S(G σ ). In this paper, we provide a new method to compare the skew energies of two oriented graphs whose skew characteristic polynomials satisfy a given recurrence relation and determine the oriented unicyclic graphs of order n with the first largest skew energies for . [Copyright &y& Elsevier]

Abstract: In 2008, Marshall (2010) settled a long-standing open problem by showing that if is a polynomial that is non-negative on the strip , then there exist sums of squares such that . In this paper, we generalize Marshall’s result to various strips and half-strips in the plane. Our results give many new examples of non-compact semialgebraic sets in for which one can characterize all polynomials which are non-negative on the set. For example, we show that if is a compact subset of the real line and a specific set of generators for as a semialgebraic set, then whenever is non-negative on , there are sums of squares such that . [Copyright &y& Elsevier]

Abstract: The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an time and polynomial space algorithm. [Copyright &y& Elsevier]

Abstract: This paper presents algorithms for decomposing any zero-dimensional polynomial set into simple sets over an arbitrary finite field, with an associated ideal or zero decomposition. As a key ingredient of these algorithms, we generalize the squarefree decomposition approach for univariate polynomials over a finite field to that over the field product determined by a simple set. As a subprocedure of the generalized squarefree decomposition approach, a method is proposed to extract the th root of any element in the field product. Experiments with a preliminary implementation show the effectiveness of our algorithms. [Copyright &y& Elsevier]

Abstract: The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. [Copyright &y& Elsevier]

Abstract: A word is a fixed point of a nontrivial morphism if and is not the identity on the alphabet of . The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed point. The algorithm also constructs the corresponding morphism, which has the smallest possible number of non-erased letters. [Copyright &y& Elsevier]

Abstract: Let be a nonempty closed set with . For and , define by and We call a super-stationary set if holds for any infinite subset of . Denoting the derived set (i.e. the set of accumulating points) of and with , it is known [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)] that for any nonempty closed subset of such that there exists an infinite subset of with , there exists an infinite subset such that is a super-stationary set. Moreover, if for any infinite subset of , then the maximal pattern complexity [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)] is . Thus, the uniform complexity functions are realized by the super-stationary sets [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)]. We call a super-subword of if there exists with such that . Let be the set of having no super-subword . Denote where . In this paper, we prove that the class of super-stationary sets other than coincides with the class of for nonempty finite sets . Moreover, it also coincides with the class of for nonempty finite sets , where is the set of minimal covers of . Using these expressions, we can calculate the complexity of super-stationary sets and prove that the complexity function of a super-stationary set in is either or a polynomial function of for large . We also discuss the word problems related to the super-subwords. [Copyright &y& Elsevier]

Abstract: Let be the chromatic polynomial of a graph . A graph is chromatically unique if for any graph , implies H is isomorphic to . For integers , , denote by the complete -partite graph that has partite sets of size and one partite set of size . Let be the set of graphs obtained from by adding a set of edges to the partite set of size such that is bipartite. If , denote the only graph in by . In this paper, we shall prove that for and , each graph is chromatically unique if and only if is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph is chromatically unique for and . [Copyright &y& Elsevier]

Abstract: This paper revisits the ‘branchwidth territories’ of Kloks, Kratochvíl and Müller [T. Kloks, J. Kratochvíl, H. Müller, New branchwidth territories, in: 16th Ann. Symp. on Theoretical Aspect of Computer Science, STACS, in: Lecture Notes in Computer Science, vol. 1563, 1999, pp. 173–183] to provide a simpler proof, and a faster algorithm for computing the branchwidth of an interval graph. We also generalize the algorithm to the class of chordal graphs, albeit at the expense of exponential running time. Compliance with the ternary constraint of the branchwidth definition is facilitated by a simple new tool called -troikas: three sets of size at most each are a -troika of set , if any two have union . We give a straightforward algorithm, computing branchwidth for an interval graph on edges, vertices and maximal cliques. We also prove a conjecture of Mazoit [F. Mazoit, A general scheme for deciding the branchwidth, Technical Report RR2004-34, LIP — École Normale Supérieure de Lyon, 2004. http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2004/RR2004-34.pdf], by showing that branchwidth can be computed in polynomial time for a chordal graph given with a clique tree having a polynomial number of subtrees. [Copyright &y& Elsevier]