VLDB 2026 Research / reviewers in the wild / expert
Steven D. Noble
dblp:06/2876
· DBLP profile ↗
10ranked-venue papers
1as first author
1since 2021 · last 2025
0000-0002-1621-0059ORCID · verified
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 10 · 1 first-author · 1 since 2021Databases, data management, data science and information retrieval · 1
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | An Activities Expansion of the Transition Polynomial of a MultimatroidabstractAbstract. The weighted transition polynomial of a multimatroid is a generalization of the Tutte polynomial. By defining the activity of a skew class with respect to a basis in a multimatroid, we obtain an activities expansion for the weighted transition polynomial. We also decompose the set of all transversals of a multimatroid as a union of subsets of transversals. Each term in the decomposition has the structure of a boolean lattice, and each transversal belongs to a number of terms depending only on the sizes of some of its skew classes. Further expressions for the transition polynomial of a multimatroid are obtained via an equivalence relation on its bases and by extending Kochol’s theory of compatible sets. We apply our multimatroid results to obtain a result of Morse about the transition polynomial of a delta-matroid and get a partition of the boolean lattice of subsets of elements of a delta-matroid determined by the feasible sets. Finally, we describe how multimatroids arise from graphs embedded in surfaces and apply our results to obtain an activities expansion for the topological transition polynomial. Our work extends results for the Tutte polynomial of a matroid. Criel Merino, Iain Moffatt, Steven D. Noble |
SIAM J. Discret. Math. | 3 |
| 2019 | The complexity of solution-free sets of integers for general linear equations
Keith J. Edwards, Steven D. Noble |
Discret. Appl. Math. | 2 |
| 2012 | The complexity of two graph orientation problems
Nicole Eggemann, Steven D. Noble |
Discret. Appl. Math. | 2 |
| 2012 | On plane graphs with link component number equal to the nullity
Yuefeng Lin, Steven D. Noble, Xian'an Jin, Wenfang Cheng |
Discret. Appl. Math. | 2 |
| 2011 | The clustering coefficient of a scale-free random graph
Nicole Eggemann, Steven D. Noble |
Discret. Appl. Math. | 2 |
| 2011 | Maximizing edge-ratio is NP-complete
Steven D. Noble, Pierre Hansen, Nenad Mladenovic |
Discret. Appl. Math. | 1 |
| 2010 | k-L(2, 1)-labelling for planar graphs is NP-complete for k>=4
Nicole Eggemann, Frédéric Havet, Steven D. Noble |
Discret. Appl. Math. | 3 |
| 2004 | Finding next-to-shortest paths in a graph
Ilia Krasikov, Steven D. Noble |
Inf. Process. Lett. | 2 |
| 2002 | Optimal arrangement of data in a tree directory
Malwina J. Luczak, Steven D. Noble |
Discret. Appl. Math. | 2 |
| 2001 | Optimal arrangement of data in a tree directory
Malwina J. Luczak, Steven D. Noble |
Discret. Appl. Math. | 2 |