Publication
Adjacent Crossings Do Matter
Related publications (36)
The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.
We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...
Elsevier2024GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation
Daniel Gatica-Perez, Sina Sajadmanesh
In this paper, we study the problem of learning Graph Neural Networks (GNNs) with Differential Privacy (DP). We propose a novel differentially private GNN based on Aggregation Perturbation (GAP), which adds stochastic noise to the GNN's aggregation functio ...
Berkeley2023A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models
Negar Kiyavash, Ehsan Mokhtarian, Saber Salehkaleybar
We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skele ...
2022Ramsey numbers of ordered graphs
An ordered graph is a pair G = (G,
ELECTRONIC JOURNAL OF COMBINATORICS2020Improved Ramsey-type results for comparability graphs
Istvan Tomon, Dániel József Korándi
Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...
CAMBRIDGE UNIV PRESS2020Avoiding long Berge cycles: the missing casesk=r+1 andk=r+2
The maximum size of anr-uniform hypergraph without a Berge cycle of length at leastkhas been determined for allk >= r+ 3 by Furedi, Kostochka and Luo and fork
2020Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves
An ordered graph G(
COMENIUS UNIV2019Ordered graphs and large bi-cliques in intersection graphs of curves
An ordered graph G(
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019Asyrnptotics for the Turan number of Berge-K-2,K-t
Let F be a graph. A hypergraph is called Berge-F if it can be obtained by replacing each edge in F by a hyperedge containing it. Let F be a family of graphs. The Turan number of the family Berge-F is the maximum possible number of edges in an r-uniform hyp ...
ACADEMIC PRESS INC ELSEVIER SCIENCE2019Edge Ordered Turan Problems
Gábor Tardos, Abhishek Methuku
We introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge or ...
COMENIUS UNIV2019