Category: MCS-208

Recent Developments in Minimum Cost Spanning Trees

1. Dynamic MST Maintenance

Recent research has focused on efficiently maintaining an MST when the underlying graph changes, without recomputing it from scratch.
Instead, these algorithms update only the affected portions of the MST when edges or weights change.
This is especially useful for dynamic networks such as real-time routing or evolving communication infrastructures, where graphs continuously change over time.

What is a Left-Leaning Red–Black Tree?

A Left-Leaning Red–Black Tree (LLRB) is a simplified form of a Red–Black Tree that enforces an additional rule:
all red links must lean left.

LLRB trees were introduced to make red–black trees easier to implement and reason about, while still maintaining balanced binary search tree properties.

[Answer of Question 2] This question is about tree traversals and how ancestor–descendant relationships are reflected in traversal orders.

We are given:

• A node m is a proper ancestor of node n
• Test condition:
  m precedes n in X-order
  m follows n in Y-order
• Where X, Y ∈ {preorder, postorder, inorder}

We must find all valid (X, Y) pairs for which this condition is always true.

Question 1 : For each of the Singly Linked List, Circularly Singly Linked List, Doubly Linked List, Circularly Doubly Linked List, write one application that is exclusively suitable for that list. For example, X may be an application for whose implementation, only Circularly Singly Linked List is suitable and others are not suitable. Justify your answer.

1. Singly Linked List (SLL)

Application: Implementation of a simple Undo feature with limited backward access (e.g., text editor undo stack)