Search results for "graphs"
showing 10 items of 126 documents
Some properties of vertex-oblique graphs
2016
The type t G ( v ) of a vertex v ? V ( G ) is the ordered degree-sequence ( d 1 , ? , d d G ( v ) ) of the vertices adjacent with v , where d 1 ? ? ? d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ? a | V ( G ) | + b holds is finite when a ? 1 and infinite when a ? 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et?al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a fun…
On lazy representations and Sturmian graphs
2011
In this paper we establish a strong relationship between the set of lazy representations and the set of paths in a Sturmian graph associated with a real number α. We prove that for any non-negative integer i the unique path weighted i in the Sturmian graph associated with α represents the lazy representation of i in the Ostrowski numeration system associated with α. Moreover, we provide several properties of the representations of the natural integers in this numeration system.
Sturmian graphs and integer representations over numeration systems
2012
AbstractIn this paper we consider a numeration system, originally due to Ostrowski, based on the continued fraction expansion of a real number α. We prove that this system has deep connections with the Sturmian graph associated with α. We provide several properties of the representations of the natural integers in this system. In particular, we prove that the set of lazy representations of the natural integers in this numeration system is regular if and only if the continued fraction expansion of α is eventually periodic. The main result of the paper is that for any number i the unique path weighted i in the Sturmian graph associated with α represents the lazy representation of i in the Ost…
Nondeterministic operations on finite relational structures
1998
Abstract This article builds on a tutorial introduction to universal algebra for language theory (Courcelle, Theoret. Comput. Sci. 163 (1996) 1–54) and extends it in two directions. First, nondeterministic operations are considered, i.e., operations which give a set of results instead of a single one. Most of their properties concerning recognizability and equational definability carry over from the ordinary case with minor modifications. Second, inductive sets of evaluations are studied in greater detail. It seems that they are handled most naturally in the framework presented here. We consider the analogues of top-down and bottom-up tree transducers. Again, most of their closure propertie…
On the hardness of optimization in power-law graphs
2008
Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…
Minimal Morse flows on compact manifolds
2006
Abstract In this paper we prove, using the Poincare–Hopf inequalities, that a minimal number of non-degenerate singularities can be computed in terms only of abstract homological boundary information. Furthermore, this minimal number can be realized on some manifold with non-empty boundary satisfying the abstract homological boundary information. In fact, we present all possible indices and types (connecting or disconnecting) of singularities realizing this minimal number. The Euler characteristics of all manifolds realizing this minimal number are obtained and the associated Lyapunov graphs of Morse type are described and shown to have the lowest topological complexity.
Online Scheduling of Task Graphs on Heterogeneous Platforms
2020
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…
Teaching English through Arts in upper secondary school : a photographic teaching material package
2017
Lukion opetussuunnitelma uudistui vuonna 2015. Uudistuneessa OPS:ssa kannustetaan oppiainerajat ylittävään laaja-alaiseen oppimiseen. Tämä tarjoaa uusia ja mielenkiintoisia lähestymistapoja kielenopettamiseen lukiossa. Tämä materiaalipaketti yhdistää kuvataiteen ja englannin kielen opettamisen valokuvauksen avulla. Valokuvia on tänä päivänä helppo ottaa, sillä lähes jokaisella on älypuhelin, johon on tavallisesti integroitu kamera. Kameran avulla oppilaat pääsevät toteuttamaan luovuuttaan, jota tällä hetkellä ei painoteta tarpeeksi opiskelussa. Valokuvaukseen pohjautuvan oppimateriaalipaketin peruspilarit ovat kommunikatiivisessa kielenopetuksessa, oppijakeskeisyydessä ja motivaation löytäm…
About Supergraphs. Part III
2019
Summary The previous articles [5] and [6] introduced formalizations of the step-by-step operations we use to construct finite graphs by hand. That implicitly showed that any finite graph can be constructed from the trivial edgeless graph K 1 by applying a finite sequence of these basic operations. In this article that claim is proven explicitly with Mizar[4].
REDUCTION OF CONSTRAINT SYSTEMS
1993
Geometric modeling by constraints leads to large systems of algebraic equations. This paper studies bipartite graphs underlaid by systems of equations. It shows how these graphs make possible to polynomially decompose these systems into well constrained, over-, and underconstrained subsystems. This paper also gives an efficient method to decompose well constrained systems into irreducible ones. These decompositions greatly speed up the resolution in case of reducible systems. They also allow debugging systems of constraints.