اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدWDM and Directed Star Arboricity
261
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A digraph is $m$-labelled if every arc is labelled by an integer in ${1, dots,m}$. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study $n$-fibre colourings of labelled digraphs. These are colourings of the arcs of $D$ such that at each vertex $v$, and for each colour $alpha$, $in(v,alpha)+out(v,alpha)leq n$ with $in(v,alpha)$ the number of arcs coloured $alpha$ entering $v$ and $out(v,alpha)$ the number of labels $l$ such that there is at least one arc of label $l$ leaving $v$ and coloured with $alpha$. The problem is to find the minimum number of colours $lambda_n(D)$ such that the $m$-labelled digraph $D$ has an $n$-fibre colouring. In the particular case when $D$ is $1$-labelled, $lambda_1(D)$ is called the directed star arboricity of $D$, and is denoted by $dst(D)$. We first show that $dst(D)leq 2Delta^-(D)+1$, and conjecture that if $Delta^-(D)geq 2$, then $dst(D)leq 2Delta^-(D)$. We also prove that for a subcubic digraph $D$, then $dst(D)leq 3$, and that if $Delta^+(D), Delta^-(D)leq 2$, then $dst(D)leq 4$. Finally, we study $lambda_n(m,k)=max{lambda_n(D) tq D mbox{is $m$-labelled} et Delta^-(D)leq k}$. We show that if $mgeq n$, then $ds leftlceilfrac{m}{n}leftlceil frac{k}{n}rightrceil + frac{k}{n} rightrceilleq lambda_n(m,k) leqleftlceilfrac{m}{n}leftlceil frac{k}{n}rightrceil + frac{k}{n} rightrceil + C frac{m^2log k}{n}$ for some constant $C$. We conjecture that the lower bound should be the right value of $lambda_n(m,k)$.
قيم البحث
اقرأ أيضاً
We demonstrate 32.5 Tbit/s 16QAM Nyquist WDM transmission over a total length of 227 km of SMF-28 without optical dispersion compensation. A number of 325 optical carriers are derived from a single laser and encoded with dual-polarization 16QAM data
using sinc-shaped Nyquist pulses. As we use no guard bands, the carriers have a spacing of 12.5 GHz equal to the Nyquist bandwidth of the data. We achieve a high net spectral efficiency of 6.4 bit/s/Hz using a software-defined transmitter which generates the electrical modulator drive signals in real-time.
Arboricity is a graph parameter akin to chromatic number, in that it seeks to partition the vertices into the smallest number of sparse subgraphs. Where for the chromatic number we are partitioning the vertices into independent sets, for the arborici
ty we want to partition the vertices into cycle-free subsets (i.e., forests). Arboricity is NP-hard in general, and our focus is on the arboricity of cographs. For arboricity two, we obtain the complete list of minimal cograph obstructions. These minimal obstructions do generalize to higher arboricities; however, we no longer have a complete list, and in fact, the number of minimal cograph obstructions grows exponentially with arboricity. We obtain bounds on their size and the height of their cotrees. More generally, we consider the following common generalization of colouring and partition into forests: given non-negative integers $p$ and $q$, we ask if a given cograph $G$ admits a vertex partition into $p$ forests and $q$ independent sets. We give a polynomial-time dynamic programming algorithm for this problem. In fact, the algorithm solves a more general problem which also includes several other problems such as finding a maximum $q$-colourable subgraph, maximum subgraph of arboricity-$p$, minimum vertex feedback set and minimum $q$ of a $q$-colourable vertex feedback set.
We give four new proofs of the directed version of Brooks Theorem and an NP-completeness result.
We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of the largest induced forest in planar graphs. In particular, the follo
wing three long-standing conjectures concern the size of a largest induced forest in a planar graph, and we conjecture that each of these can be generalized to the setting of fractional vertex-arboricity. In 1979, Albertson and Berman conjectured that every planar graph has an induced forest on at least half of its vertices, in 1987, Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest on at least five-eighths of its vertices, and in 2010, Kowalik, Luv{z}ar, and v{S}krekovski conjectured that every planar graph of girth at least five has an induced forest on at least seven-tenths of its vertices. We make progress toward the fractional generalization of the latter of these, by proving that every planar graph of girth at least five has fractional vertex-arboricity at most $2 - 1/324$.
Let $G$ be a graph and $S, T subseteq V(G)$ be (possibly overlapping) sets of terminals, $|S|=|T|=k$. We are interested in computing a vertex sparsifier for terminal cuts in $G$, i.e., a graph $H$ on a smallest possible number of vertices, where $S c
up T subseteq V(H)$ and such that for every $A subseteq S$ and $B subseteq T$ the size of a minimum $(A,B)$-vertex cut is the same in $G$ as in $H$. We assume that our graphs are unweighted and that terminals may be part of the min-cut. In previous work, Kratsch and Wahlstrom (FOCS 2012/JACM 2020) used connections to matroid theory to show that a vertex sparsifier $H$ with $O(k^3)$ vertices can be computed in randomized polynomial time, even for arbitrary digraphs $G$. However, since then, no improvements on the size $O(k^3)$ have been shown. In this paper, we draw inspiration from the renowned Bollobass Two-Families Theorem in extremal combinatorics and introduce the use of total orderings into Kratsch and Wahlstroms methods. This new perspective allows us to construct a sparsifier $H$ of $Theta(k^2)$ vertices for the case that $G$ is a DAG. We also show how to compute $H$ in time near-linear in the size of $G$, improving on the previous $O(n^{omega+1})$. Furthermore, $H$ recovers the closest min-cut in $G$ for every partition $(A,B)$, which was not previously known. Finally, we show that a sparsifier of size $Omega(k^2)$ is required, both for DAGs and for undirected edge cuts.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
