Polynomial bounds for the grid-minor theorem
One of the key results in Robertson and Seymour's seminal work on graph minors is the grid-
minor theorem (also called the excluded grid theorem). The theorem states that for every …
minor theorem (also called the excluded grid theorem). The theorem states that for every …
An O (k^ 3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
In the Survivable Network Design problem (SNDP), we are given an undirected graph G (V,
E) with costs on edges, along with a connectivity requirement r (u, v) for each pair u, v of …
E) with costs on edges, along with a connectivity requirement r (u, v) for each pair u, v of …
Online node-weighted steiner tree and related problems
We obtain the first online algorithms for the node-weighted Steiner tree, Steiner forest and
group Steiner tree problems that achieve a poly-logarithmic competitive ratio. Our algorithm …
group Steiner tree problems that achieve a poly-logarithmic competitive ratio. Our algorithm …
Excluded grid theorem: Improved and simplified
J Chuzhoy - Proceedings of the forty-seventh annual ACM …, 2015 - dl.acm.org
We study the Excluded Grid Theorem of Robertson and Seymour. This is a fundamental
result in graph theory, that states that there is some function f: Z+→ Z+, such that for any …
result in graph theory, that states that there is some function f: Z+→ Z+, such that for any …
Bounds for the zero-forcing number of graphs with large girth
We investigate the zero-forcing number for triangle-free graphs. We improve upon the trivial
bound, $\delta\le Z (G) $ where $\delta $ is the minimum degree, in the triangle-free case. In …
bound, $\delta\le Z (G) $ where $\delta $ is the minimum degree, in the triangle-free case. In …
Improved bounds for the excluded grid theorem
J Chuzhoy - arXiv preprint arXiv:1602.02629, 2016 - arxiv.org
We study the Excluded Grid Theorem of Robertson and Seymour. This is a fundamental
result in graph theory, that states that there is some function $ f: Z^+\rightarrow Z^+ $, such …
result in graph theory, that states that there is some function $ f: Z^+\rightarrow Z^+ $, such …
Artificial intelligence and machine learning generated conjectures with TxGraffiti
R Davila - arXiv preprint arXiv:2407.02731, 2024 - arxiv.org
\emph {TxGraffiti} is a machine learning and heuristic based artificial intelligence designed
to automate the task of conjecturing in mathematics. Since its inception, TxGraffiti has …
to automate the task of conjecturing in mathematics. Since its inception, TxGraffiti has …
[HTML][HTML] On the total forcing number of a graph
R Davila, MA Henning - Discrete Applied Mathematics, 2019 - Elsevier
A total forcing set in a graph G is a forcing set (zero forcing set) in G which induces a
subgraph without isolated vertices. Total forcing sets were introduced and first studied by …
subgraph without isolated vertices. Total forcing sets were introduced and first studied by …
Poly-logarithmic approximation for maximum node disjoint paths with constant congestion
Abstract We consider the Maximum Node Disjoint Paths (MNDP) problem in undirected
graphs. The input consists of an undirected graph G=(V, E) and a collection {(s 1, t 1),…,(sk …
graphs. The input consists of an undirected graph G=(V, E) and a collection {(s 1, t 1),…,(sk …
Bounds on the connected forcing number of a graph
In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph.
The minimum cardinality of such a set is called the connected forcing number of the graph …
The minimum cardinality of such a set is called the connected forcing number of the graph …