Discrete Mathematics· 2026Q1
Yönlendirilmiş dal-genişliği: Ağaç-genişliğinin yönlendirilmiş bir analoğu
Directed branch-width: A directed analogue of tree-width
- 1atıf
- Q1SCImago
- 2026yıl
Kısa özet
Araştırmacılar, yönlendirilmiş çizge genişliği için yeni bir ölçüt olan yönlendirilmiş dal-genişliğini tanıttı; bu ölçüt, yönlendirilmemiş ağaç-genişliğinden farklıdır ve algoritmik sonuçların daha geniş bir çizge sınıfına genişletilmesini sağlar.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- Yönlendirilmiş çizge'ler için yeni bir genişlik ölçütü olan yönlendirilmiş dal-genişliğini tanıtır.
- Yönlendirilmiş dal-genişliği, yönlendirilmemiş ağaç-genişliğinden farklıdır ve onu sınırlayamaz.
- Ölçüt, kaynaklar ve lavabolar dışında ağaç-genişliğinden farklıdır.
- Algoritmik sonuçların sınırlı yönlendirilmiş dal-genişliğine sahip çizge'lere genişletilmesini sağlar.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
Gurski and Wanke showed that a graph class C has bounded tree-width if and only if its associated class of directed line graphs has bounded clique-width. Inevitably -- asking whether this relationship lifts to directed graphs -- we introduce a new digraph width measure: we obtain it by investigating digraphs whose directed line graphs have bounded cliquewidth. Thus, to generalize Gurski and Wanke's aforementioned result, we introduce a natural generalization of branch-width to digraphs and we name it accordingly. Directed branch-width is a genuinely directed width-measure insofar as it cannot be used to bound the value of the underlying undirected tree-width. Despite this, the two measures are still closely related: the directed branch-width of a digraph D can differ from the branch-width of its underlying undirected graph only at sources and sinks. This relationship allows us to extend a range of algorithmic results from directed graphs with bounded underlying treewidth to the strictly larger class of digraphs having bounded directed branch-width.
Yazarların özeti; kaynağından alınmıştır. Discrete Mathematics, 2026 · DOI ↗
Ücretsiz hesapla devam et
Makaleye Sor ile bu makaleye günde 3 soru ücretsiz; makaleyi kaydet, kaynakçasını al, ilgi alanına göre her gün yeni özetler. Çıkarımlar Premium.
Web'de ücretsiz devam etGoogle ya da Apple hesabınla giriş; kart istemez. Bu makaleye geri dönersin.
Telefonda:
Alan: Hesaplamalı Kuram ve Matematik
Computational Theory and MathematicsComputer Science