Browsing Department of Informatics by Journals "Theoretical Computer Science"
Now showing items 1-9 of 9
-
A complexity dichotomy for critical values of the b-chromatic number of graphs
(Journal article; Peer reviewed, 2020)A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has ... -
Computational complexity aspects of super domination
(Journal article; Peer reviewed, 2023)Let G be a graph. A dominating set D ⊆ V (G) is a super dominating set if for every vertex x ∈ V (G) \ D there exists y ∈ D such that NG (y) ∩ (V (G) \ D)) = {x}. The cardinality of a smallest super dominating set of G is ... -
The directed 2-linkage problem with length constraints
(Journal article; Peer reviewed, 2020) -
Looking at the Stars
(Journal article, 2006-02-28)The problem of packing k vertex-disjoint copies of a graph H into another graph G is NP-complete if H has more than two vertices in some connected component. In the framework of parameterized complexity we analyze a ... -
Loop-checking and the uniform word problem for join-semilattices with an inflationary endomorphism
(Journal article; Peer reviewed, 2022)We solve in polynomial time two decision problems that occur in type checking when typings depend on universe level constraints. -
Mim-Width III. Graph powers and generalized distance domination problems
(Peer reviewed; Journal article, 2019)We generalize the family of (σ,ρ) problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as Distance-r Dominating Set and Distance-r Independent ... -
On the effectiveness of the incremental approach to minimal chordal edge modification
(Journal article; Peer reviewed, 2021)Because edge modification problems are computationally difficult for most target graph classes, considerable attention has been devoted to inclusion-minimal edge modifications, which are usually polynomial-time computable ... -
Resolute control: Forbidding candidates from winning an election is hard
(Journal article; Peer reviewed, 2022) -
A type system for counting instances of software components
(Peer reviewed; Journal article, 2012)We identify an abstract language for component software based on process algebra. Besides the usual operators for sequential, alternative and parallel composition, it has primitives for instantiating components and for ...