Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 7

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  graph theory
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Dynamic optimization on a set of permutations

100%
Zorychta K.
Mathematica Applicanda
|
1977
|
tom 5
|
nr 9
PL
Artykuł nie zawiera streszczenia
EN
The classical problem of optimization on the permutation set is considered. The specific approach of the author is based on representing permutations as integer nonnegative solutions of the equation 2x0.+ 2x1 +...+2xn=2n-1 the objective function is assumed to be in the form f(x)= ∑i=0n-1fi(xi,xi+1), which allows the use of dynamic programming. MR0525712  
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Dürer polyhedra: the dark side of melancholia

80%
Fowler P., John P.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
101-109
EN
Dürer's engraving Melencolia I famously includes a perspective view of a solid polyhedral block of which the visible portion is an 8-circuit bounding a pentagon-triple+triangle patch. The polyhedron is usually taken to be a cube truncated on antipodal corners, but an infinity of others are compatible with the visible patch. Construction of all cubic polyhedra compatible with the visible portion (i.e., Dürer Polyhedra) is discussed, explicit graphs and symmetries are listed for small cases ( ≤ 18 vertices) and total counts are given for 10 ≤ vertices ≤ 26.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Proof Compression and NP Versus PSPACE II: Addendum

80%
Gordeev L., Haeusler E. H.
Bulletin of the Section of Logic
|
2022
|
tom 51
|
nr 2
197-205
EN
In our previous work we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier’s cut-free sequent calculus for minimal logic (HSC) with the horizontal compressing in the corresponding minimal Prawitz-style natural deduction (ND). In this Addendum we show how to prove a weaker result NP = coNP without referring to HSC. The underlying idea (due to the second author) is to omit full minimal logic and compress only “naive” normal tree-like ND refutations of the existence of Hamiltonian cycles in given non-Hamiltonian graphs, since the Hamiltonian graph problem in NPcomplete. Thus, loosely speaking, the proof of NP = coNP can be obtained by HSC-elimination from our proof of NP = PSPACE.
4
Content available remote

Reverse mathematics of some topics from algorithmic graph theory

80%
Clote P. G., Hirst J. L.
Fundamenta Mathematicae
|
1998
|
tom 157
|
nr 1
1-13
EN
This paper analyzes the proof-theoretic strength of an infinite version of several theorems from algorithmic graph theory. In particular, theorems on reachability matrices, shortest path matrices, topological sorting, and minimal spanning trees are considered.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Linear and cyclic radio k-labelings of trees

80%
Kchikech M., Khennoufa R., Togni O.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
105-123
EN
Motivated by problems in radio channel assignments, we consider radio k-labelings of graphs. For a connected graph G and an integer k ≥ 1, a linear radio k-labeling of G is an assignment f of nonnegative integers to the vertices of G such that $|f(x)-f(y)| ≥ k+1-d_G(x,y)$, for any two distinct vertices x and y, where $d_G(x,y)$ is the distance between x and y in G. A cyclic k-labeling of G is defined analogously by using the cyclic metric on the labels. In both cases, we are interested in minimizing the span of the labeling. The linear (cyclic, respectively) radio k-labeling number of G is the minimum span of a linear (cyclic, respectively) radio k-labeling of G. In this paper, linear and cyclic radio k-labeling numbers of paths, stars and trees are studied. For the path Pₙ of order n ≤ k+1, we completely determine the cyclic and linear radio k-labeling numbers. For 1 ≤ k ≤ n-2, a new improved lower bound for the linear radio k-labeling number is presented. Moreover, we give the exact value of the linear radio k-labeling number of stars and we present an upper bound for the linear radio k-labeling number of trees.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On k-intersection edge colourings

80%
Muthu R., Narayanan N., Subramanian C.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
411-418
EN
We propose the following problem. For some k ≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ'ₖ(G). Let fₖ be defined by $fₖ(Δ) = max_{G : Δ(G) = Δ} {χ'ₖ(G)}$. We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Radio k-labelings for Cartesian products of graphs

61%
Kchikech M., Khennoufa R., Togni O.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 1
165-178
EN
Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that $|f(x)-f(y)| ≥ k+1-d_G(x,y)$, for any two vertices x and y, where $d_G(x,y)$ is the distance between x and y in G. The radio k-chromatic number is the minimum of max{f(x)-f(y):x,y ∈ V(G)} over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian product of two graphs, providing upper bounds on the radio k-chromatic number for this product. These results help to determine upper and lower bounds for radio k-chromatic numbers of hypercubes and grids. In particular, we show that the ratio of upper and lower bounds of the radio number and the radio antipodal number of the square grid is asymptotically [3/2].
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.