Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 An equitable partition into branchings in a digraph is a partition of the arc set into branchings such that the sizes of any two branchings differ at most by one.
Kenjiro Takazawa
doaj +1 more source
Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign $-$ if and only if its endpoints are in different parts.
Luerbio Faria +3 more
doaj +1 more source
Approximating optimization problems in graphs with locational uncertainty [PDF]
Discrete Mathematics & Theoretical Computer ScienceMany combinatorial optimization problems can be formulated as the search for a subgraph that satisfies certain properties and minimizes the total weight. We assume here that the vertices correspond to points in a metric space and can take any position in
Marin Bougeret +2 more
doaj +1 more source
The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 The Permutation Pattern Matching problem, asking whether a pattern permutation $\pi$ is contained in a permutation $\tau$, is known to be NP-complete. In this paper we present two polynomial time algorithms for special cases.
Michael H. Albert +3 more
doaj +1 more source
Special Issue on Algorithms and Data-Structures for Compressed Computation
Algorithms, 2022 As the production of massive data has outpaced Moore’s law in many scientific areas, the very notion of algorithms is transforming [...]
Alberto Policriti, Nicola Prezza
doaj +1 more source
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 Graphs and ...
Serge Gaspers, Mathieu Liedloff
doaj +1 more source
Lightweight Reconstruction of Urban Buildings: Data Structures, Algorithms, and Future Directions
IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2023 Commercial buildings as well as residential houses represent core structures of any modern day urban or semiurban areas. Consequently, 3-D models of urban buildings are of paramount importance to a majority of digital urban applications, such as city ...
Vivek Kamra +5 more
doaj +1 more source
Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 In a barter exchange market, agents bring items and seek to exchange their items with one another. Agents may agree to a k-way exchange involving a cycle of k agents.
Timothy Highley, Hoang Le
doaj +1 more source
Tight Euler tours in uniform hypergraphs - computational aspects [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set $e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on indices are computed ...
Zbigniew Lonc +2 more
doaj +1 more source
FEBS Letters, EarlyView.Dimeric pyruvate formate‐lyase cleaves pyruvate using a radical‐based mechanism. G734 serves as a radical storage location, and the radical is transferred to the catalytic C419 residue. Mutation of the C418‐C419 pair causes loss of enzyme activity, but does not impede radical introduction onto G734. Therefore, cis‐ but not trans‐radical transfer occurs
Michelle Kammel +2 more
wiley +1 more source