Results 11 to 20 of about 147,152 (326)
Parameterized Complexity of Gerrymandering [PDF]
, 2022 In a representative democracy, the electoral process involves partitioning geographical space into districts which each elect a single representative. These representatives craft and vote on legislation, incentivizing political parties to win as many districts as possible (ideally a plurality). Gerrymandering is the process by which district boundaries
Andrew Fraser +2 more
openalex +3 more sources
Parameterized Complexity of Geodetic Set
Journal of Graph Algorithms and Applications, 2022 A vertex set $S$ of a graph $G$ is geodetic if every vertex of $G$ lies on a shortest path between two vertices in $S$. Given a graph $G$ and $k \in \mathbb{N}$, the NP-hard ${\rm G{\small EODETIC}~S{ \small ET}}$ problem asks whether there is a geodetic set of size at most $k$.
Leon Kellerhals, Tomohiro Koana
openalex +5 more sources
Parameterized Proof Complexity [PDF]
computational complexity, 2007 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Dantchev, S., Martin, B., Szeider, S.
openaire +2 more sources
On the parameterized complexity of Grid Contraction
Journal of Computer and System Sciences, 2022 For a family of graphs $\mathcal{G}$, the $\mathcal{G}$-\textsc{Contraction} problem takes as an input a graph $G$ and an integer $k$, and the goal is to decide if there exists $F \subseteq E(G)$ of size at most $k$ such that $G/F$ belongs to $\mathcal{G}$. Here, $G/F$ is the graph obtained from $G$ by contracting all the edges in $F$. In this article,
Saket Saurabh +2 more
openaire +6 more sources
Parameterized complexity of synchronization and road coloring [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 Automata, Logic and ...
Vojtěch Vorel, Adam Roman
doaj +1 more source
Parameterized Complexity of Diameter [PDF]
Algorithmica, 2019 AbstractDiameter—the task of computing the length of a longest shortest path—is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no $$O(n^{1.99})$$ O ( n 1.99
Bentert, Matthias, Nichterlein , André
openaire +4 more sources
On the Descriptive Complexity of Color Coding
Algorithms, 2021 Color coding is an algorithmic technique used in parameterized complexity theory to detect “small” structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color ...
Max Bannach, Till Tantau
doaj +1 more source
Clique Transversal Variants on Graphs: A Parameterized-Complexity Perspective
Mathematics, 2023 The clique transversal problem and its variants have garnered significant attention in the last two decades due to their practical applications in communication networks, social-network theory and transceiver placement for cellular telephones.
Chuan-Min Lee
doaj +1 more source
Algorithms, 2020 In this paper, we study the relationship of parameterized enumeration complexity classes defined by Creignou et al. (MFCS 2013). Specifically, we introduce two hierarchies (IncFPTa and CapIncFPTa) of enumeration complexity classes for incremental fpt ...
Arne Meier
doaj +1 more source
On the Parameterized Complexity of Compact Set Packing. [PDF]
Algorithmica, 2023 AbstractThe Set Packing problem is, given a collection of sets $$\mathcal {S}$$ S over a ground set U, to find a maximum collection of sets that are pairwise disjoint. The problem is among the most fundamental NP-hard optimization problems that have been studied extensively in various computational regimes.
Gadekar A.
europepmc +5 more sources