<p>One thing that immediately comes to mind is that graph k-coloring is used in compilers for register allocation. An instance of register allocation for k registers is solved by reducing into an instance of k-coloring. See, for example, section 8.8 of Aho, Lam, Sethi and Ullman (i.e. Dragon Book).</p>

CC BY-SA 3.0
2018-04-14T09:35:39.400Z
I think this is true for many NP-complete (NP-hard by extension) problems. Travelling Salesman, Vehicle Routing, Scheduling,... and many of its variations arise from real-life problems. These real-life problems are often discussed (as they should) in the papers that introduce/discuss the problem/variation. e.g. https://set.kuleuven.be/codes/itsp_page and related paper https://arxiv.org/abs/1701.08517
Auberon
CC BY-SA 3.0
2018-04-15T08:01:43.657Z
@Auberon Indeed. I listed register allocation just because it's a rather unusual (and non-intuitive) instance of graph coloring!
xrq
CC BY-SA 3.0
2018-04-07T00:24:11.957Z
2018-04-07T00:24:11.957Z
xrq
<p>There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used in many papers that are not about complexity theory. This is an indication of the general usefulness and importance of the concept. </p>

<p>Similarly, network flow algorithms, shortest path algorithms etc.,  have combinatorial optimization as their home area, but are also used in many papers that are not specifically about combinatorial optimization. Graphs have graph theory as their home area, but are used in many other fields, as well.</p>

<p><strong>Question:</strong> What are some other, not so obvious or not so well known examples of methods/concepts that also proved useful outside of their home areas?</p>

<cc.complexity-theory><reference-request><graph-theory><combinatorics>
Results/concepts that also proved useful outside of their "home areas"
Andras Farago
# Results/concepts that also proved useful outside of their "home areas"

(Asked by: username_0 on 2018-04-06)

There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used in many papers that are not about complexity theory. This is an indication of the general usefulness and importance of the concept.

Similarly, network flow algorithms, shortest path algorithms etc., have combinatorial optimization as their home area, but are also used in many papers that are not specifically about combinatorial optimization. Graphs have graph theory as their home area, but are used in many other fields, as well.

**Question:** What are some other, not so obvious or not so well known examples of methods/concepts that also proved useful outside of their home areas?

**Tags:** cc.complexity-theory, reference-request, graph-theory, combinatorics


---

## 1 answers

### Answer by username_1 on 2018-04-07. Score: 4

One thing that immediately comes to mind is that graph k-coloring is used in compilers for register allocation. An instance of register allocation for k registers is solved by reducing into an instance of k-coloring. See, for example, section 8.8 of Aho, Lam, Sethi and Ullman (i.e. Dragon Book).

> **Comments:**
> **username_2**: I think this is true for many NP-complete (NP-hard by extension) problems. Travelling Salesman, Vehicle Routing, Scheduling,... and many of its variations arise from real-life problems. These real-life problems are often discussed (as they should) in the papers that introduce/discuss the problem/variation. e.g. https://set.kuleuven.be/codes/itsp_page and related paper https://arxiv.org/abs/1701.08517  
> **username_1**: @username_2 Indeed. I listed register allocation just because it's a rather unusual (and non-intuitive) instance of graph coloring!  

---

