Sorting with constraints
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911134820335616 |
|---|---|
| author | Manas, A. |
| author_facet | Manas, A. |
| contents | In this work, we study the generalized sorting problem, where we are given a set of $n$ elements to be sorted, but only a subset of all possible pairwise element comparisons is allowed. We look at the problem from the perspective of the graph formed by the ``forbidden'' pairs, and we parameterize algorithms using the clique number and the chromatic number of this graph. We also extend these results to the class of problems where the input graph is not necessarily sortable, and one is only interested in discovering the partial order. We use our results to develop a simple algorithm that always determines the underlying partial order in $O(n^{3/2} \log n)$ probes, when the input graph is an Erdős--Rényi graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02616 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sorting with constraints Manas, A. Data Structures and Algorithms Discrete Mathematics In this work, we study the generalized sorting problem, where we are given a set of $n$ elements to be sorted, but only a subset of all possible pairwise element comparisons is allowed. We look at the problem from the perspective of the graph formed by the ``forbidden'' pairs, and we parameterize algorithms using the clique number and the chromatic number of this graph. We also extend these results to the class of problems where the input graph is not necessarily sortable, and one is only interested in discovering the partial order. We use our results to develop a simple algorithm that always determines the underlying partial order in $O(n^{3/2} \log n)$ probes, when the input graph is an Erdős--Rényi graph. |
| title | Sorting with constraints |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2509.02616 |