Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUbergraphs: A Definition of a Recursive Hypergraph Structure
55
0
0.0
(
0
)
Added by
Kathleen Nowak
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Partly in service of exploring the formal basis for Georgetown Universitys AvesTerra database structure, we formalize a recursive hypergraph data structure, which we call an ubergraph.
rate research
Read More
The Hales numbered $n$-dimensional hypercube and the corresponding adjacency matrix exhibit interesting recursive structures in $n$. These structures lead to a very simple proof of the well-known bandwidth formula for hypercube, whose proof was thought to be surprisingly difficult. A related problem called hypercube antibandwidth, for which Harper proposed an algorithm, is also reexamined in the light of the above recursive structures, and a close form solution is found.
We propose a new ternary infinite (even full-infinite) square-free sequence. The sequence is defined both by an iterative method and by a direct definition. Both definitions are analogous to those of the Thue-Morse sequence. The direct definition is given by a deterministic finite automaton with output. In short, the sequence is automatic.
This paper is devoted to the study of the dynamics of a discrete system related to some self stabilizing protocol on a ring of processors.
A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomial-time certifying recognition algorithm is known to date, despite such algorithms being found for many subclasses of circular-arc graphs. This is largely due to the fact that a forbidden structure characterization of circular-arc graphs is not known, even though the problem has been intensely studied since the seminal work of Klee in the 1960s. In this contribution, we settle this problem. We present the first forbidden structure characterization of circular-arc graphs. Our obstruction has the form of mutually avoiding walks in the graph. It naturally extends a similar obstruction that characterizes interval graphs. As a consequence, we give the first polynomial-time certifying algorithm for the recognition of circular-arc graphs.
We work on a parallelizable time-orientable Lorentzian 4-manifold and prove that in this case the notion of spin structure can be equivalently defined in a purely analytic fashion. Our analytic definition relies on the use of the concept of a non-degenerate two-by-two formally self-adjoint first order linear differential operator and gauge transformations of such operators. We also give an analytic definition of spin structure for the 3-dimensional Riemannian case.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
