research
∙
07/03/2023
Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem
We introduce and study a new optimization problem on digraphs, termed Ma...
share
research
∙
05/11/2023
Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems
We investigate the difficulty of finding economically efficient solution...
research
∙
04/26/2023
Acceleration for Timing-Aware Gate-Level Logic Simulation with One-Pass GPU Parallelism
Witnessing the advancing scale and complexity of chip design and benefit...
research
∙
04/20/2023
Bounds on Maximum Weight Directed Cut
We obtain lower and upper bounds for the maximum weight of a directed cu...
research
∙
10/14/2022
(1,1)-Cluster Editing is Polynomial-time Solvable
A graph H is a clique graph if H is a vertex-disjoin union of cliques. A...
research
∙
07/25/2022
A Survey on Graph Problems Parameterized Above and Below Guaranteed Values
We survey the field of algorithms and complexity for graph problems para...
research
∙
07/25/2022
Results on the Small Quasi-Kernel Conjecture
A quasi-kernel of a digraph D is an independent set Q⊆ V(D) such that fo...
research
∙
01/30/2022
Solving Routing Problems via Important Cuts
We introduce a novel approach of using important cuts which allowed us t...
research
∙
01/22/2022
Strong subgraph 2-arc-connectivity and arc-strong connectivity of Cartesian product of digraphs
Let D=(V,A) be a digraph of order n, S a subset of V of size k and 2≤ k≤...
research
∙
12/31/2021
Preference Swaps for the Stable Matching Problem
An instance I of the Stable Matching Problem (SMP) is given by a biparti...
research
∙
11/18/2021
Extended Path Partition Conjecture for Semicomplete and Acyclic Compositions
Let D be a digraph and let λ(D) denote the number of vertices in a longe...
research
∙
06/10/2021
Valued Authorization Policy Existence Problem: Theory and Experiments
Recent work has shown that many problems of satisfiability and resilienc...
research
∙
05/07/2021
Solving the Workflow Satisfiability Problem using General Purpose Solvers
The workflow satisfiability problem (WSP) is a well-studied problem in a...
research
∙
05/01/2021
Perfect Forests in Graphs and Their Extensions
Let G be a graph on n vertices. For i∈{0,1} and a connected graph G, a s...
research
∙
04/13/2021
Towards Better Understanding of User Authorization Query Problem via Multi-variable Complexity Analysis
User authorization queries in the context of role-based access control h...
research
∙
04/12/2021
Lower Bounds for Maximum Weighted Cut
While there have been many results on lower bounds for Max Cut in unweig...
research
∙
11/11/2020
Kings in Multipartite Hypertournaments
In his paper "Kings in Bipartite Hypertournaments" (Graphs & Combinatori...
research
∙
09/17/2020
p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
We introduce and study two natural generalizations of the Connected Vert...
research
∙
06/23/2020
Approximation algorithms for general cluster routing problem
Graph routing problems have been investigated extensively in operations ...
research
∙
01/28/2020
Proximity and Remoteness in Directed and Undirected Graphs
Let D be a strongly connected digraph. The average distance σ̅(v) of a v...
research
∙
07/28/2019
Parameterized Pre-coloring Extension and List Coloring Problems
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the p...
research
∙
06/19/2019
Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs
A digraph D=(V, A) has a good pair at a vertex r if D has a pair of arc-...
research
∙
04/15/2019
Bounded and Approximate Strong Satisfiability in Workflows
There has been a considerable amount of interest in recent years in the ...
research
∙
03/28/2019
Arc-disjoint Strong Spanning Subdigraphs of Semicomplete Compositions
A strong arc decomposition of a digraph D=(V,A) is a decomposition of it...
research
∙
12/20/2018
Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs
A digraph D=(V,A) has a good decomposition if A has two disjoint sets A_...
research
∙
08/08/2018
Strong Subgraph Connectivity of Digraphs: A Survey
In this survey we overview known results on the strong subgraph k-connec...
research
∙
06/24/2018
On r-Simple k-Path and Related Problems Parameterized by k/r
Abasi et al. (2014) and Gabizon et al. (2015) studied the following prob...
research
∙
05/04/2018
Strong subgraph k-arc-connectivity
Two previous papers, arXiv:1803.00284 and arXiv:1803.00281, introduced a...
research
∙
05/04/2018
Lower and Upper Bound for Computing the Size of All Second Neighbourhoods
We consider the problem of computing the size of each r-neighbourhood fo...
research
∙
04/27/2018
Alternative parameterizations of Metric Dimension
A set of vertices W in a graph G is called resolving if for any two dist...
research
∙
03/01/2018
Strong Subgraph k-connectivity
Generalized connectivity introduced by Hager (1985) has been studied ext...
research
∙
03/01/2018
Strong subgraph k-connectivity bounds
Let D=(V,A) be a digraph of order n, S a subset of V of size k and 2< k≤...
research
∙
01/15/2018