research
∙
07/20/2023
Small But Unwieldy
We show that for any natural number s, there is a constant γ and a subgr...
share
research
∙
07/10/2023
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
We prove a characterization of the structural conditions on matrices of ...
research
∙
03/08/2023
Graph parameters, implicit representations and factorial properties
How to efficiently represent a graph in computer memory is a fundamental...
research
∙
02/22/2023
Graphs with minimum fractional domatic number
The domatic number of a graph is the maximum number of vertex disjoint d...
research
∙
01/23/2023
Functionality of box intersection graphs
Functionality is a graph complexity measure that extends a variety of pa...
research
∙
12/19/2022
Compact Graph Representation of molecular crystals using Point-wise Distance Distributions
Use of graphs to represent molecular crystals has become popular in rece...
research
∙
06/06/2022
Optimal Adjacency Labels for Subgraphs of Cartesian Products
For any hereditary graph class ℱ, we construct optimal adjacency labelin...
research
∙
05/30/2022
Giant Components in Random Temporal Graphs
A temporal graph is a graph whose edges appear only at certain points in...
research
∙
02/15/2022
The treewidth and pathwidth of graph unions
For two graphs G_1 and G_2 on the same vertex set [n]:={1,2, …, n}, and ...
research
∙
11/05/2021
Randomized Communication and the Implicit Graph Conjecture
The most basic lower-bound question in randomized communication complexi...
research
∙
03/12/2021
Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication
We give lower bounds on the communication complexity of graph problems i...
research
∙
11/07/2020
Sharp Thresholds in Random Simple Temporal Graphs
A graph whose edges only appear at certain points in time is called a te...
research
∙
10/08/2020
Succinct Permutation Graphs
We present a succinct, i.e., asymptotically space-optimal, data structur...
research
∙
05/17/2020
Matching in Stochastically Evolving Graphs
This paper studies the maximum cardinality matching problem in stochasti...
research
∙
04/13/2020
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
In this paper we consider the following total functional problem: Given ...
research
∙
10/11/2019
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
Let vc(G), fvs(G) and oct(G), respectively, denote the size of a minimum...
research
∙
07/30/2019
Linear Programming complementation and its application to fractional graph theory
In this paper, we introduce a new kind of duality for Linear Programming...
research
∙
05/13/2019
Computing Maximum Matchings in Temporal Graphs
We study the computational complexity of finding maximum-cardinality tem...
research
∙
03/08/2019
How fast can we reach a target vertex in stochastic temporal graphs?
Temporal graphs are used to abstractly model real-life networks that are...
research
∙
11/12/2018
Sliding Window Temporal Graph Coloring
Graph coloring is one of the most famous computational problems with app...
research
∙
05/24/2018
Linear read-once and related Boolean functions
It is known that a positive Boolean function f depending on n variables ...
research
∙
05/17/2018
Deleting edges to restrict the size of an epidemic in temporal networks
A variety of potentially disease-spreading contact networks can be natur...
research
∙
05/11/2018
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
We give deterministic distributed (1+ϵ)-approximation algorithms for Min...
research
∙
04/27/2018
Letter graphs and geometric grid classes of permutations: characterization and recognition
In this paper, we reveal an intriguing relationship between two seemingl...
research
∙
02/20/2018