English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We give deterministic distributed $(1+\epsilon)$-approximation algorithms forMinimum Vertex Coloring and Maximum Independent Set on chordal graphs in theLOCAL model. Our coloring algorithm runs in $O(\frac{1}{\epsilon} \log n)$rounds, and our independent set algorithm has a runtime of$O(\frac{1}{\epsilon}\log(\frac{1}{\epsilon})\log^* n)$ rounds. For coloring,existing lower bounds imply that the dependencies on $\frac{1}{\epsilon}$ and$\log n$ are best possible. For independent set, we prove that$O(\frac{1}{\epsilon})$ rounds are necessary.  Both our algorithms make use of a tree decomposition of the input chordalgraph. They iteratively peel off interval subgraphs, which are identified viathe tree decomposition of the input graph, thereby partitioning the vertex setinto $O(\log n)$ layers. For coloring, each interval graph is coloredindependently, which results in various coloring conflicts between the layers.These conflicts are then resolved in a separate phase, using the particularstructure of our partitioning. For independent set, only the first $O( \log\frac{1}{\epsilon})$ layers are required as they already contain a large enoughindependent set. We develop a $(1+\epsilon)$-approximation maximum independentset algorithm for interval graphs, which we then apply to those layers.  This work raises the question as to how useful tree decompositions are fordistributed computing.

Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs