Iskanje po repozitoriju

Perfect phylogenies via the minimum uncovering branching problem : efficiently solvable cases
Narmina Baghirova, Esther Galby, Martin Milanič, 2025, izvirni znanstveni članek

Opis: In this paper, we present new efficiently solvable cases of the Minimum Uncovering Branching problem, an optimization problem with applications in cancer genomics introduced by Hujdurovi´c, Husi´c, Milaniˇc, Rizzi, and Tomescu in 2018. The problem involves a family of finite sets, and the goal is to map each non-maximal set to exactly one set that contains it, minimizing the sum of uncovered elements across all sets in the family. Hujdurovi´c et al. formulated the problem in terms of branchings of the digraph formed by the proper set inclusion relation on the input sets and studied the problem complexity based on properties of the corresponding partially ordered set, in particular, with respect to its height and width, defined respectively as the maximum cardinality of a chain and an antichain. They showed that the problem is APX-complete for instances of bounded height and that a constant-factor approximation algorithm exists for instances of bounded width, but left the exact complexity for bounded-width instances open. In this paper, we answer this question by proving that the problem is solvable in polynomial time. We derive this result by examining the structural properties of optimal solutions and reducing the problem to computing maximum matchings in bipartite graphs and maximum weight antichains in partially ordered sets. We also introduce a new polynomially computable lower bound and identify another condition for polynomial-time solvability.
Ključne besede: perfect phylogeny, branching, partially ordered set, antichain, width
Objavljeno v RUP: 13.10.2025; Ogledov: 291; Prenosov: 3
Celotno besedilo (793,74 KB)
Gradivo ima več datotek! Več...

Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theorem
Ademir Hujdurović, Martin Milanič, Edin Husić, Romeo Rizzi, Alexandru I. Tomescu, 2017, objavljeni povzetek znanstvenega prispevka na konferenci

Ključne besede: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 3864; Prenosov: 125
Povezava na celotno besedilo

Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theorem
Martin Milanič, 2018, objavljeni povzetek znanstvenega prispevka na konferenci (vabljeno predavanje)

Ključne besede: perfect phylogeny, NP-hard problem, graph coloring, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 3456; Prenosov: 22
Povezava na celotno besedilo

An extension of the classification of evolutionarily singular strategies in adaptive dynamics
Barbara Boldin, Odo Diekmann, 2018, objavljeni povzetek znanstvenega prispevka na konferenci

Ključne besede: adaptive dynamics, mathematical model, evolutionarily singular strategy, evolutionary branching
Objavljeno v RUP: 03.08.2018; Ogledov: 3972; Prenosov: 34
Povezava na celotno besedilo

Stability of cellular automata trajectories revisited : branching walks and Lyapunov profile
Jan M. Baetens, Janko Gravner, 2016, izvirni znanstveni članek

Ključne besede: asymptotic shape, branching walk, cellular automaton, doubly periodic configuration, large deviations, Lyapunov exponent, percolation, stability
Objavljeno v RUP: 02.03.2018; Ogledov: 4126; Prenosov: 132
Povezava na celotno besedilo