We consider a tomographic problem on graphs, called Minimum Surgical Probing , introduced by Bar-Noy et al. [4]. Each vertex v ∈ V of a graph G = ( V , E ) is associated with an (unknown) label ℓ v . The outcome of probing a vertex v is P v = ∑ u ∈ N [ v ] ℓ u , where N [ v ] denotes the closed neighborhood of v . The goal is to uncover the labels given probes P v for all v ∈ V . For some graphs, the labels cannot be determined (uniquely), and the use of surgical probes is permitted but must be minimized. A surgical probe at vertex v returns ℓ v . In this paper, we introduce convexity constraints to Minimum Surgical Probing . For binary labels, convexity imposes constraints such as if ℓ u = ℓ v = 1 , then for all vertices w on a shortest path between u and v , we must have that ℓ w = 1 . We show that convexity constraints reduce the number of required surgical probes for several graph families. Specifically, they allow us to recover the labels without using surgical probes for trees and bipartite graphs where otherwise ⌊| V |/2⌋ surgical probes might be needed. Our analysis is based on restricting the size of cliques in a graph using the concept of K h -free graphs (forbidden induced subgraphs). Utilizing this approach, we analyze grid graphs , the King’s graph , and (maximal-) outerplanar graphs .

In 2013, while studying a relevant class of polyominoes that tile the plane by translation, i.e., double square polyominoes, Blondin Massé et al. found that their boundary words, encoded by the Freeman chain coding on a four letters alphabet, have specific interesting properties that involve notions of combinatorics on words such as palindromicity, periodicity and symmetry. Furthermore, they defined a notion of reducibility on double squares using homologous morphisms, so leading to a set of irreducible tile elements called prime double squares. The authors, by inspecting the boundary words of the smallest prime double squares, conjectured the strong property that no runs of two (or more) consecutive equal letters are present there. In this paper, we prove such a conjecture using combinatorics on words’ tools, and setting the path to the definition of a fast generation algorithm and to the possibility of enumerating the elements of this class w.r.t. standard parameters, as perimeter and area.

In this paper we consider rectangular billiard tables having vertices with integer coordinates, and side lengths equal to integer multiples of the norms of the side directions. We also assume that all the bouncing points of a billiard ball are constrained to belong to the integer lattice Z2. We address several questions concerning combinatorial and geometric properties of the allowed orbits, that, due to the integer constraint, are called integer orbits. We give a complete classification of integer orbits, and the parameters contributing to their structure are precisely determined. This leads to understand how the orbit fills the lattice billiard before it really propagates. In particular, one can characterize the trajectories that reach a billiard pocket, as well as all the closed orbits, by the simple knowledge of the size of the billiard table, and of the starting moving direction. The characterization bases on the explicit determination of the numerical sequences corresponding to clockwise, and counterclockwise, bouncing. We also investigate the geometrical structure of an allowed orbit in terms of special sub-patterns, called Z-paths, pointing out the allowed lengths of different Z-paths in a same orbit. This is of independent interest, and is related to the configurations known as switching components, that play a crucial role in discrete tomography, and in problems concerning image reconstruction.

Given a 3-uniform hypergraph H , its 2-intersection graph G has as vertex set the hyperedges of H and e e ′ is an edge of G whenever e and e ′ have exactly two common vertices in H . Di Marco et al. prove in Di Marco et al. (2023) that deciding whether a graph G is the 2-intersection graph of a 3-uniform hypergraph is N P -complete. Following this result, we study the class of claw-free graphs. We show that the recognition problem remains N P -complete for that class, but becomes polynomial if we consider triangulated claw-free graphs.

International audience

Abstract Given a 3-uniform hypergraph H having a set V of vertices, and a set of hyperedges $$T\subset \mathcal {P}(V)$$ T ⊂ P ( V ) , whose elements have cardinality three each, a null labelling is an assignment of $$\pm 1$$ ± 1 to the hyperedges such that each vertex belongs to the same number of hyperedges labelled $$+1$$ + 1 and $$-1$$ - 1 . A sufficient condition for the existence of a null labelling of H (proved in Di Marco et al. Lect Notes Comput Sci 12757:282–294, 2021) is a Hamiltonian cycle in its 2-intersection graph. The notion of 2-intersection graph generalizes that of intersection graph of an (hyper)graph and extends its effectiveness. The present study first shows that this sufficient condition for the existence of a null labelling in H can not be weakened by requiring only the connectedness of the 2-intersection graph. Then some interesting properties related to their clique configurations are proved. Finally, the main result is proved, the NP-completeness of this characterization and, as a consequence, of the construction of the related 3-hypergraphs.

The study of the compressibility of repetitive sequences is an issue that is attracting great interest. We consider purely morphic words, which are highly repetitive sequences generated by iterating a morphism$\varphi$that admits a fixed point (denoted by$\varphi^{\infty}(a)$) starting from a given character$a$belonging to the finite alphabet$A$, i.e.$\varphi^{\infty}(a)=\lim\nolimits_{i\rightarrow\infty}\varphi^{i}(a)$. Such morphisms are called prolongable on$a$. Here we focus on the compressibility via the Burrows-Wheeler Transform ($BWT$) of infinite families of finite sequences generated by morphisms. In particular, denoted by$r(w)$the number of equal-letter runs of a word$w$, we provide new upper bounds on$r(\mathsf{bwt} (\varphi^{i}(a)))$, i.e. the number of equal-letter runs produced when$BWT$is applied on$\varphi^{i}(a)$. Such bounds depend on the factor complexity$f_{x}(n)$of the infinite word$x=\varphi^{\infty}(a)$, that counts, for each$n\geq 0$, the number of distinct factors of$x$having length$n$.

It is commonly accepted that the various parts of the human brain interact as a network at macroscopic, mesoscopic and microscopic level. Recently, different network models have been proposed to mime the brain behavior both at resting state and during tasks: Our study concerns one of those model th at consider both the physical and functional connectivity as well as topological metrics of the brain networks. We provide evidence of the soundness of the model by means of a synthetic dataset based on the existing literature concerning the active cerebral areas at the resting state. Furthermore, we consider Ruzicka similarity measure in order to stress the predictive capability of the model and provide a thresholding criterium. Some network statistics are finally provided.

In discrete tomographic image reconstruction, projections are taken along a finite set S of valid directions for a working grid 𝒜. In general, uniqueness cannot be achieved in the whole grid 𝒜. Usually, some information on the object to be reconstructed is introduced, that, sometimes, allows possib le ambiguities to be removed. From a different perspective, one aims in finding subregions of 𝒜 where uniqueness can be guaranteed, and obtained in linear time, only from the knowledge of S. When S consists of two lattice directions, the shape of any such region of uniqueness, say ROU, have been completely characterized in previous works by means of a double Euclidean division algorithm called DEDA. Results have been later extended to special triples of directions, under a suitable assumption on their entries. In this paper we remove the previous assumption, so providing a complete characterization of the shape of the ROU for such kind of triples. We also show that the employed strategy can be even applied to more general sets of three directions, where the corresponding ROU can be characterized as well. Independently of the combinatorial interest of the problem, the result can be exploited to define in advance, namely before using any kind of radiation, suitable sets of directions that allow regions of interest to be included in the corresponding ROU. Results have been proved in all details, and several experiments are considered, in order to support the theoretical steps and to clarify possible applications.

This article introduces an analogue of permutation classes in the context of polyominoes. For both permutation classes and polyomino classes, we present an original way of characterizing them by avoidance constraints (namely, with excluded submatrices) and we discuss how canonical such a description by submatrix-avoidance can be. We provide numerous examples of permutation and polyomino classes which may be defined and studied from the submatrix-avoidance point of view, and conclude with various directions for future research on this topic.

Starting from a Theorem by Hall, we define the identity transform of a permutation π as C(π) = (0 + π(0), 1 + π(1), ..., (n − 1) + π(n − 1)), and we define the set Cn = {(C(π) : π ∈ Sn}, where Sn is the set of permutations of the elements of the cyclic group ℤn. In the first part of this paper we s tudy the set Cn: we show some closure properties of this set, and then provide some of its combinatorial and algebraic characterizations and connections with other combinatorial structures. In the second part of the paper, we use some of the combinatorial properties we have determined to provide a different algorithm for the proof of Hall’s Theorem.

International audience

Image reconstruction from collected data is an inverse problem that frequently appears in several applications.It is encountered in various research areas, such as biomedical imaging, reconstruction algorithms, image processing, stereology, and mathematical morphology.It turns out that the same methodologies and strategies can be frequently adapted to different frames and disciplines.One of the main tools is the Radon Transform, and its inversion formula which is used, in particular, in many problems of tomographic research where the information is usually acquired by means of data obtained from X-rays projections.Since the 1990s specialistic meetings have been organized devoted to both theoretical advances and practical applications of Tomography.Among them, the Meeting on Tomography and Applications, now in its 6th edition, succeeds in attracting some of the main researchers involved in the various aspects of Tomography.The presentations consists of technical contributions as well as talks outlining the state-ofthe-arts and proposing future research directions.The main purpose of this edition of the meeting was to focus on connections and overlaps among Discrete Tomography, Geometric Tomography, and Computerized Tomography, with a special focus on applications.This special issue consists of invited papers.Some of them have been presented at the 6th Meeting on Tomography and Applications held at Politecnico di Milano on April 26-27, 2012, but in order to provide a better perspective on current research also additional papers were invited.The papers went through a thorough refereeing process and the accepted papers are presented in this issue.The reminder of this preface consists of two parts.In the first part we provide brief overviews for each of the papers from this issue.In the second part we provide summaries for talks presented at the 6th Meeting on Tomography and Applications.In this way the reader can get a better insight into the nature of the meeting and hence also into the current research in the area covered by this special issue.This paper exploits the possibilities of using the Discrete Algebraic Reconstruction Technique (DART) that performs extremely well for the discrete tomography reconstruction problem, with the data obtained from the Magnetic Resonance imaging (MRI).The MRI is a well-known technique that uses a magnetic field to produce images of various structures like organs, soft tissues, bone, or biological samples.The actual M RI reconstruction methods either use fast inversion Fourier transform techniques from a huge number of measurements, or apply compressed sensing methods that use few measurements, but must be used under some a priori assumptions.In this paper a new type of a prior knowledge about the homogeneity of the unknown structure (that reflects the poorness of grey levels in the MRI image) is exploited.The authors adapt the DART technique to this scenario, they carry on experiments on MRI data obtaining extremely accurate reconstructions, and they prove that DART outperforms a commonly used reconstruction method.• K.J. Batenburg, W. Fortes, and R. Tijdeman, Approximate discrete reconstruction algorithm.The paper presents an approximate algorithm to reconstruct images with a small number of grey levels from projections, i.e., quantitative data on the number of pixels, weighted with respect to their grey level, along a finite set of directions.This problem is one of the most studied in the field of Discrete Tomography, and a range of reconstruction algorithms have been proposed in the literature with most of them assuming the presence of only two grey levels.However, since the general problem is not polynomially solvable, all these algorithms do not guarantee the exact reconstruction of the image, and moreover the error, i.e., the misclassified pixels, depends on the particular problem instance and so it cannot be bounded sharply.The authors approach the reconstruction problem by means of a mixed technique that relies both on algebraic methods for the solution of linear equation systems and on combinatorics.The algorithm they define requires that the grey levels of the image belong to a fixed set of real values.The reconstructed solution is really close to the unknown starting image, and the difference between the given projections and the projections of this reconstructed image is bounded.A remarkable fact is that this bound is explicitly computable, and moreover it is independent of the image size and scales linearly with the number of projection angles.• R.A. Fiorini, and G. Laguteta, Discrete Tomography Data Footprint Reduction by Information Conservation.The authors deal with the problem concerning the storage of a huge amount of collected data.One of the aims of Discrete Tomography is the reconstruction of nanocrystals at atomic resolution.This is carried out through suitable algorithms which allow a fast and accurate reconstruction from a limited number of projection images.These algorithms produce a large amount of available data, and one of the underlying problems is their storage in a smaller space.The usually employed processes to achieve this are known as Data Footprint Reduction (DFR), including, for instance, deduplication and lossless compression.However, they fail to match high end data imaging application requirements, so that no contemporary lossless compression/decompression algorithm is completely satisfactory.In this paper a proposal is presented for an original and convenient algorithm for numeric images that offers both Arbitrary Bit Depth (ABD) resolution and Dynamic Upscale Regeneration (DUR), with full information conservation, at no extra computational cost.An original application example is presented and critically discussed.

In this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once. Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter 2(n+2) satisfies the rational recurrence relation fn =4fn−1 −2fn−2, with f0 =1, f1 =2, f2 =7. Moreover, we give a combinatorial interpretation of this statement. In the last section, we present some open problems.