FIFO Branch-and-Bound Uses a Queue

A Branch-and-Bound strategy organizes live nodes according to a node-selection rule. In the FIFO variant, nodes are expanded in the exact order they were generated, which matches breadth-first search behavior.2 Therefore, the correct data structure for FIFO Branch-and-Bound is (ii) Queue.2

This classification is standard in algorithm literature:

• FIFO Branch-and-Bound $\rightarrow$ Queue2
• LIFO Branch-and-Bound $\rightarrow$ Stack2
• Least-Cost Branch-and-Bound $\rightarrow$ Priority Queue2

The key reason is semantic: FIFO means first in, first out. If a node is inserted earlier, it must be removed earlier. A queue enforces exactly that discipline.2

A useful way to visualize the control logic is:

Because nodes are processed level by level, FIFO Branch-and-Bound behaves like a bounded BFS over the state-space tree, while still using pruning rules to eliminate unpromising nodes.2

Answer: (ii) Queue.2

Footnotes

1. Introduction to Branch and Bound - Data Structures and Algorithms Tutorial - GeeksforGeeks - Explains FIFO, LIFO, and least-cost Branch-and-Bound; states FIFO uses a queue and behaves like BFS. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. Branch and Bound - George Washington University PDF - Lecture notes defining Branch-and-Bound terminology and distinguishing queue, stack, and least-cost strategies. ↩ ↩² ↩³

3. BRANCH AND BOUND (ON THE WEB) - University of Florida PDF - Describes FIFO Branch-and-Bound with an explicit live-node queue and front-pop behavior. ↩ ↩² ↩³ ↩⁴

4. UNIT-4 Part – I : Branch and Bound PDF - States BFS-like search is FIFO using a queue, while D-search-like search is LIFO using a stack. ↩ ↩²

5. Data Structures - Priority Queues PDF - Defines priority queues and their role in removing elements by key priority rather than insertion order. ↩

To understand why the answer is a queue, it helps to distinguish the three classic node-selection policies in Branch-and-Bound.2

In Branch-and-Bound terminology, an E-node is the node whose children are currently generated, and a dead node is one that has already been expanded or pruned.2 FIFO control does not rank nodes by quality; it simply removes the oldest live node first. That is why several academic notes describe FIFO and LIFO policies as comparatively “blind” selection rules when contrasted with least-cost search.2

This matters when interpreting the multiple-choice options:

• Stack is incorrect because a stack gives LIFO, not FIFO.2
• Queue is correct because it preserves insertion order.2
• Priority Queue is used for least-cost or best-bound selection, not plain FIFO.2
• Array is not the defining abstract data structure here; although a queue can be implemented with an array, the algorithmic strategy itself is described as using a queue.2

Footnotes

1. Introduction to Branch and Bound - Data Structures and Algorithms Tutorial - GeeksforGeeks - Explains FIFO, LIFO, and least-cost Branch-and-Bound; states FIFO uses a queue and behaves like BFS. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. Branch and Bound - George Washington University PDF - Lecture notes defining Branch-and-Bound terminology and distinguishing queue, stack, and least-cost strategies. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. BRANCH AND BOUND (ON THE WEB) - University of Florida PDF - Describes FIFO Branch-and-Bound with an explicit live-node queue and front-pop behavior. ↩ ↩²

4. UNIT-4 Part – I : Branch and Bound PDF - States BFS-like search is FIFO using a queue, while D-search-like search is LIFO using a stack. ↩ ↩² ↩³ ↩⁴

5. Data Structures - Priority Queues PDF - Defines priority queues and their role in removing elements by key priority rather than insertion order. ↩ ↩² ↩³

A compact pseudocode sketch makes the data-structure choice explicit:2

$$\text{Initialize queue } Q$$ $$\text{enqueue}(Q,\ \text{root})$$ $$\text{while } Q \neq \emptyset:$$ $$\quad u \leftarrow \text{dequeue}(Q)$$ $$\quad \text{generate children of } u$$ $$\quad \text{for each feasible child } v:$$ $$\qquad \text{if } v \text{ is not pruned, enqueue}(Q, v)$$

The queue operations are the defining signal:

• insertion at the rear,
• deletion from the front,
• oldest node expanded first.

That operational behavior is incompatible with a stack, where removal happens from the top, and incompatible with a priority queue, where removal depends on key order rather than age.2

Footnotes

1. BRANCH AND BOUND (ON THE WEB) - University of Florida PDF - Describes FIFO Branch-and-Bound with an explicit live-node queue and front-pop behavior. ↩ ↩²

2. UNIT-4 Part – I : Branch and Bound PDF - States BFS-like search is FIFO using a queue, while D-search-like search is LIFO using a stack. ↩ ↩²

3. Data Structures - Priority Queues PDF - Defines priority queues and their role in removing elements by key priority rather than insertion order. ↩

A final conceptual summary:

So, for the question:

“A FIFO Branch-and-Bound strategy is typically implemented using which data structure?”

the academically correct and standard answer is:

$$\boxed{\text{(ii) Queue}}$$

This answer is supported consistently across tutorials, lecture notes, and standard algorithm texts discussing FIFO, LIFO, and LC variants of Branch-and-Bound.3

Footnotes

1. Introduction to Branch and Bound - Data Structures and Algorithms Tutorial - GeeksforGeeks - Explains FIFO, LIFO, and least-cost Branch-and-Bound; states FIFO uses a queue and behaves like BFS. ↩

2. Branch and Bound - George Washington University PDF - Lecture notes defining Branch-and-Bound terminology and distinguishing queue, stack, and least-cost strategies. ↩

3. BRANCH AND BOUND (ON THE WEB) - University of Florida PDF - Describes FIFO Branch-and-Bound with an explicit live-node queue and front-pop behavior. ↩