Steven D. Noble

dblp:06/2876 · DBLP profile ↗
← Back
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
YearPublicationVenuePosition
2025 An Activities Expansion of the Transition Polynomial of a Multimatroid
abstract
Abstract. 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