Near-optimal distributed dominating set in bounded arboricity graphs

Near-optimal distributed dominating set in bounded arboricity graphs

Abstract We describe a simple deterministic $$O( \varepsilon ^{-1} \log \Delta )$$ O ( ε...

Descrizione completa

Dettagli Bibliografici
Autori principali:	Dory, Michal, Ghaffari, Mohsen, Ilchi, Saeed
Altri autori:	Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Natura:	Articolo
Lingua:	English
Pubblicazione:	Springer Berlin Heidelberg 2023
Accesso online:	https://hdl.handle.net/1721.1/150786

Documenti analoghi

Near-domination in graphs
di: Reed, B, et al.
Pubblicazione: (2019)

Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time
di: Ghaffari, Mohsen, et al.
Pubblicazione: (2024)

Proceedings of the Ann Arbor Graph Theory Conference held in Ann Arbor, 1968 /
di: Ann Arbor Graph Theory Conference (2nd : 1968 :Ann Arbor, Mich), et al.
Pubblicazione: (1969)

A Near-Optimal Deterministic Distributed Synchronizer
di: Ghaffari, Mohsen, et al.
Pubblicazione: (2023)

The linear arboricity of graphs with low treewidth
di: Xiang Tan, et al.
Pubblicazione: (2024-01-01)

Linear arboricity of 1-planar graphs
di: Weifan Wang, et al.
Pubblicazione: (2024-01-01)

Dominating Sets and Domination Polynomials of Graphs
di: Alikhani, Saeid
Pubblicazione: (2009)

Bounds on Co-Independent Liar’s Domination in Graphs
di: K. Suriya Prabha, et al.
Pubblicazione: (2021-01-01)

Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs
di: Fu-Tao Hu, et al.
Pubblicazione: (2024-01-01)

New Bounds on the Triple Roman Domination Number of Graphs
di: M. Hajjari, et al.
Pubblicazione: (2022-01-01)

Bounds on the global double Roman domination number in graphs
di: Guoliang Hao, et al.
Pubblicazione: (2024-01-01)

Minimal graphs with disjoint dominating and total dominating sets
di: Michael A. Henning, et al.
Pubblicazione: (2024-01-01)

Improved distributed algorithms for fundamental graph problems
di: Ghaffari, Mohsen
Pubblicazione: (2017)

Nearly Work-Efficient Parallel DFS in Undirected Graphs
di: Ghaffari, Mohsen, et al.
Pubblicazione: (2023)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
di: Ghaffari, Mohsen, et al.
Pubblicazione: (2024)

On Locating-Dominating Set of Regular Graphs
di: Anuwar Kadir Abdul Gafur, et al.
Pubblicazione: (2021-01-01)

End super dominating sets in graphs
di: Saieed Akbari, et al.
Pubblicazione: (2025-01-01)

Augmenting graphs to partition their vertices into a total dominating set and an independent dominating set
di: Teresa W. Haynes, et al.
Pubblicazione: (2025-03-01)

Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs.
di: McDiarmid, C, et al.
Pubblicazione: (2001)

Graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set
di: Teresa W. Haynes, et al.
Pubblicazione: (2024-04-01)

The game of arboricity
di: Tomasz Bartnicki, et al.
Pubblicazione: (2005-01-01)

Niche and interspecific association of dominant arbor species in Quercus communities in the Qinling Mountains, China
di: Ruizhi Huang, et al.
Pubblicazione: (2025-01-01)

Perfect Roman {3}-Domination in Graphs: Complexity and Bound of Perfect Roman {3}-Domination Number of Trees
di: Ahlam Almulhim
Pubblicazione: (2024-01-01)

Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
di: Didem Gözüpek, et al.
Pubblicazione: (2017-08-01)

Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
di: Hamamache Kheddouci, et al.
Pubblicazione: (2008-01-01)

Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
di: Hamamache Kheddouci, et al.
Pubblicazione: (2008-01-01)

Domination (set and Number) in Neutrosophic Soft over Graphs
di: Amir sabir majeed, et al.
Pubblicazione: (2022-12-01)

New Bounds for Three Outer-Independent Domination-Related Parameters in Cactus Graphs
di: Abel Cabrera-Martínez, et al.
Pubblicazione: (2024-03-01)

On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width
di: M. Rajaati, et al.
Pubblicazione: (2018-07-01)

Bounds on contention management in radio networks
di: Ghaffari, Mohsen
Pubblicazione: (2013)

Irreversible 2-conversion set in graphs of bounded degree
di: Jan Kynčl, et al.
Pubblicazione: (2017-09-01)

Arboreal categories and resources
di: Abramsky, S, et al.
Pubblicazione: (2021)

Arboreal Attachment/Detachment
di: Marroum, Marianne
Pubblicazione: (2022-12-01)

Toward an Arboreal Poetics
di: Moe, Aaron M.
Pubblicazione: (2022-12-01)

Local Arboreal Representations
di: Anderson, Jacqueline, et al.
Pubblicazione: (2018)

An Intermediate Value Theorem for the Arboricities
di: Avapa Chantasartrassmee, et al.
Pubblicazione: (2011-01-01)

Art and Reality in The Arbor (2010)
di: Mello Cecília
Pubblicazione: (2016-09-01)

On the VC-dimension of half-spaces with respect to convex sets
di: Nicolas Grelier, et al.
Pubblicazione: (2021-08-01)

Outer-Convex Dominating Set in the Corona of Graphs as Encryption Key Generator
di: Zehui Shao, et al.
Pubblicazione: (2020-01-01)

Analysis of a greedy heuristic for finding small dominating sets in graphs
Pubblicazione: (2002)