Exploiting bounded signal flow for graph orientation based on cause-effect pairs
Algorithms for Molecular Biology, 2011 Background We consider the following problem: Given an undirected network and a set of sender-receiver pairs, direct all edges such that the maximum number of "signal flows" defined by the pairs can be routed respecting edge directions.
Niedermeier Rolf +4 more
doaj +1 more source
Vertex and edge covers with clustering properties: complexity and algorithms [PDF]
, 2009 We consider the concepts of a t-total vertex cover and a t-total edge cover (t≥1), which generalise the notions of a vertex cover and an edge cover, respectively.
Fernau, Henning +3 more
core +1 more source
On the parameterized complexity of diverse SAT
Theoretical Computer Science27 pages, 5 figures; this is full version of the corresponding paper accepted and presented at the 35th International Symposium on Algorithms and Computation (ISAAC 2024)
Neeldhara Misra +2 more
openaire +4 more sources
Closed Sets and Operators thereon: Representations, Computability and Complexity [PDF]
Logical Methods in Computer Science, 2018 The TTE approach to Computable Analysis is the study of so-called representations (encodings for continuous objects such as reals, functions, and sets) with respect to the notions of computability they induce.
Carsten Rösnick-Neugebauer
doaj +1 more source
Parameterized Complexity of Deletion to Scattered Graph Classes [PDF]
, 2020 Graph-modification problems, where we add/delete a small number of vertices/edges to make the given graph to belong to a simpler graph class, is a well-studied optimization problem in all algorithmic paradigms including classical, approximation and ...
Majumdar, Diptapriyo +2 more
core +1 more source
Parameterized Model-checking of Discrete-Timed Networks and Symmetric-Broadcast Systems [PDF]
Logical Methods in Computer ScienceWe study the complexity of the model-checking problem for parameterized discrete-timed systems with arbitrarily many anonymous and identical processes, with and without a distinguished "controller", and communicating via synchronous rendezvous.
Benjamin Aminof +3 more
doaj +1 more source
Parameterized Complexity of Graph Constraint Logic [PDF]
, 2015 Graph constraint logic is a framework introduced by Hearn and Demaine, which provides several problems that are often a convenient starting point for reductions.
van der Zanden, Tom C.
core +1 more source
Streaming deletion problems parameterized by vertex cover [PDF]
, 2023 Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al ...
Oostveen, Jelle, van Leeuwen, Erik Jan
core
Randomized Parameterized Algorithms for the Kidney Exchange Problem
Algorithms, 2019 In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries.
Mugang Lin +3 more
doaj +1 more source
Computing nash equilibria gets harder : new results show hardness even for parameterized complexity
, 2009 In this paper we show that some decision problems regarding the computation of Nash equilibria are to be considered particularly hard. Most decision problems regarding Nash equilibria have been shown to be NP-complete. While some NP-complete problems can
Parsa, Mahdi, Estivill-Castro, Vladimir
core