Results 1 to 10 of about 4,947 (113)
Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 An equitable coloring of a graph $G=(V,E)$ is a (proper) vertex-coloring of $G$, such that the sizes of any two color classes differ by at most one. In this paper, we consider the equitable coloring problem in block graphs.
Hanna Furmańczyk, Vahan Mkrtchyan
doaj +1 more source
A Parameterized Approximation Algorithm for the Chromatic k-Median Problem
IEEE Access, 2021 Chromatic $k$ -median is a frequently encountered problem in the determination of the topological structures of chromosomes. This problem considers a set $\mathcal {C}$ of colored clients and a set $\mathcal {F}$ of facilities located in a metric ...
Zhen Zhang, Jinchuan Zhang, Lingzhi Zhu
doaj +1 more source
Journal of Graph Algorithms and Applications, 2022 In the classical partial vertex cover problem, we are given a graph $G$ and two positive integers $k_1$ and $k_2$. The goal is to check whether there is a subset $V'$ of $V$ of size at most $k_1$, such that $V'$ covers at least $k_2$ edges of $G$.
Vahan Mkrtchyan, Garik Petrosyan
doaj +1 more source
On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A mixed dominating set for a graph $G = (V,E)$ is a set $S\subseteq V \cup E$ such that every element $x \in (V \cup E) \backslash S$ is either adjacent or incident to an element of $S$. The mixed domination number of a graph $G$, denoted by $\gamma_m(G)$
M. Rajaati +3 more
doaj +1 more source
Practical Access to Dynamic Programming on Tree Decompositions
Algorithms, 2019 Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood.
Max Bannach, Sebastian Berndt
doaj +1 more source
Computing L(p,1)-Labeling with Combined Parameters
Journal of Graph Algorithms and Applications, 2022 Given a graph, an $L(p,1)$-labeling of the graph is an assignment $f$ from the vertex set to the set of nonnegative integers such that for any pair of vertices $u$ and $v$, $|f (u) - f (v)| \ge p$ if $u$ and $v$ are adjacent, and $f(u) \neq f(v)$ if $u ...
Tesshu Hanaka +2 more
doaj +1 more source
Phylogenetic incongruence through the lens of Monadic Second Order logic
Journal of Graph Algorithms and Applications, 2016 Within the field of phylogenetics there is growing interest in measures for summarising the dissimilarity, or incongruence, of two or more phylogenetic trees. Many of these measures are NP-hard to compute and this has stimulated a considerable volume of
Steven Kelk +3 more
doaj +1 more source
Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
Journal of Graph Algorithms and Applications, 2018 We investigate crossing minimization for $1$-page and $2$-page book drawings. We show that computing the $1$-page crossing number is fixed-parameter tractable with respect to the number of crossings, that testing $2$-page planarity is fixed-parameter ...
Michael Bannister, David Eppstein
doaj +1 more source
Graph Motif Problems Parameterized by Dual
Journal of Graph Algorithms and Applications, 2020 Let $G=(V,E)$ be a vertex-colored graph, where $C$ is the set of colors used to color $V$. The ${\rm G{\small RAPH}~M{\small OTIF}}$ (or $\rm GM$) problem takes as input $G$, a multiset $M$ of colors built from $C$, and asks whether there is a ...
Guillaume Fertin, Christian Komusiewicz
doaj +1 more source
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