Amalgams and χ‐Boundedness

A class of graphs is hereditary if it is closed under isomorphism and induced subgraphs. A class of graphs is χ‐bounded if there exists a function such that for all graphs , and all induced subgraphs H of G, we have that . We prove that proper homogeneous sets, clique‐cutsets, and amalgams together preserve χ‐boundedness. More precisely, we show that if and are hereditary classes of graphs such that is χ‐bounded, and such that every graph in either belongs to or admits a proper homogeneous set, a clique‐cutset, or an amalgam, then the class is χ‐bounded. This generalizes a result of [J Combin Theory Ser B 103(5) (2013), 567–586], which states that proper homogeneous sets and clique‐cutsets together preserve χ‐boundedness, as well as a result of [European J Combin 33(4) (2012), 679–683], which states that 1‐joins preserve χ‐boundedness. The house is the complement of the four‐edge path. As an application of our result and of the decomposition theorem for “cap‐free” graphs from [J Graph Theory 30(4) (1999), 289–308], we obtain that if G is a graph that does not contain any subdivision of the house as an induced subgraph, then .     

Relations Between Relaxation Modulus and Creep Compliance in Anisotropic Linear Viscoelasticity

The results obtained previously for scalar and class P completely monotone relaxation moduli are extended to arbitrary anisotropy. It is shown for general anisotropic viscoelastic media that, if the relaxation modulus is a locally integrable completely monotone function, then the creep compliance is a Bernstein function and conversely. The elastic and equilibrium limits of the two material functions are related to each other. The relaxation modulus or its derivative can be singular at 0. A rigorous general formulation of the relaxation spectrum in an anisotropic viscoelastic medium is given. The effect of Newtonian viscosity on creep compliance is examined. Put some makeup on him and lay him to rest. Anonymous     

Complexification phenomenon in an example of sensitive singular perturbationPhénomène de complexification dans un exemple de perturbation singulière sensitive

We consider singular perturbation problems depending on a parameter ε?0 such that for ε>0 the solution u^ε belongs to a Sobolev space on a domain $\text{Ω}$, but the limit u⁰ is not a distribution on $\text{Ω}$. A very simple model problem, solvable by Fourier transform allows us to study the complexification process of u^ε as $\text{ε↘0}$. The limit holds in the topology of a space of analytical functionals. To cite this article: C.A. De Souza, É. Sanchez-Palencia, C. R. Mecanique 332 (2004).     

Maximal admissible faces and asymptotic bounds for the normal surface solution space

The enumeration of normal surfaces is a key bottleneck in computational three-dimensional topology. The underlying procedure is the enumeration of admissible vertices of a high-dimensional polytope, where admissibility is a powerful but non-linear and non-convex constraint. The main results of this paper are significant improvements upon the best known asymptotic bounds on the number of admissible vertices, using polytopes in both the standard normal surface coordinate system and the streamlined quadrilateral coordinate system.To achieve these results we examine the layout of admissible points within these polytopes. We show that these points correspond to well-behaved substructures of the face lattice, and we study properties of the corresponding “admissible faces”. Key lemmata include upper bounds on the number of maximal admissible faces of each dimension, and a bijection between the maximal admissible faces in the two coordinate systems mentioned above.     

On the complexity of enumerating pseudo-intents

We investigate whether the pseudo-intents of a given formal context can efficiently be enumerated. We show that they cannot be enumerated in a specified lexicographic order with polynomial delay unless P=NP. Furthermore we show that if the restriction on the order of enumeration is removed, then the problem becomes at least as hard as enumerating minimal transversals of a given hypergraph. We introduce the notion of minimal pseudo-intents and show that recognizing minimal pseudo-intents is polynomial. Despite their less complicated nature, surprisingly it turns out that minimal pseudo-intents cannot be enumerated in output-polynomial time unless P=NP.     

Complexity issues for the sandwich homogeneous set problem

Graph sandwich problems were introduced by Golumbic et al. (1994) in [12] for DNA physical mapping problems and can be described as follows. Given a property Π of graphs and two disjoint sets of edges E₁, E₂ with E₁⊆E₂ on a vertex set V, the problem is to find a graph G on V with edge set E_s having property Π and such that E₁⊆E_s⊆E₂.In this paper, we exhibit a quasi-linear reduction between the problem of finding an independent set of size k≥2 in a graph and the problem of finding a sandwich homogeneous set of the same size k. Using this reduction, we prove that a number of natural (decision and counting) problems related to sandwich homogeneous sets are hard in general. We then exploit a little further the reduction and show that finding efficient algorithms to compute small sandwich homogeneous sets would imply substantial improvement for computing triangles in graphs.     

Hamiltonian index is NP-complete

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.     

Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling

We extend the classical linear assignment problem to the case where the cost of assigning agent j to task i is a multiplication of task i’s cost parameter by a cost function of agent j. The cost function of agent j is a linear function of the amount of resource allocated to the agent. A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. We prove that our assignment problem is NP-hard for three of the four variations, even if all the resource consumption weights are equal. However, and somewhat surprisingly, we find that the fourth variation is solvable in polynomial time. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has been an open question until now, for three of the four variations.     

Complexity spaces as quantitative domains of computation

We study domain theoretic properties of complexity spaces. Although the so-called complexity space is not a domain for the usual pointwise order, we show that, however, each pointed complexity space is an ω-continuous domain for which the complexity quasi-metric induces the Scott topology, and the supremum metric induces the Lawson topology. Hence, each pointed complexity space is both a quantifiable domain in the sense of M. Schellekens and a quantitative domain in the sense of P. Waszkiewicz, via the partial metric induced by the complexity quasi-metric.