Source author record

Orlando Lee

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A family of counterexamples for a conjecture of Berge on $α$ -diperfect digraphs

Let $D$ be a digraph. A stable set $S$ of $D$ and a path partition $\mathcal{P}$ of $D$ are orthogonal if every path $P \in \mathcal{P}$ contains exactly one vertex of $S$ . In 1982, Berge defined the class of $α$ -diperfect digraphs. A digraph $D$ is $α$ -diperfect if for every maximum stable set $S$ of $D$ there is a path partition $\mathcal{P}$ of $D$ orthogonal to $S$ and this property holds for every induced subdigraph of $D$ . An anti-directed odd cycle is an orientation of an odd cycle $(x_0,\ldots,x_{2k},x_0)$ with $k\geq2$ in which each vertex $x_0,x_1,x_2,x_3,x_5,x_7\ldots,x_{2k-1}$ is either a source or a sink. Berge conjectured that a digraph $D$ is $α$ -diperfect if and only if $D$ does not contain an anti-directed odd cycle as an induced subdigraph. In this paper, we show that this conjecture is false by exhibiting an infinite family of orientations of complements of odd cycles with at least seven vertices that are not $α$ -diperfect.

preprint2016arXiv

Facility Leasing with Penalties

In this paper we study the facility leasing problem with penalties. We present a primal-dual algorithm which is a 3-approximation, based on the algorithm by Nagarajan and Williamson for the facility leasing problem and on the algorithm by Charikar et al. for the facility location problem with penalties.

preprint2016arXiv

On Linial's Conjecture for Spine Digraphs

In this paper we introduce a superclass of split digraphs, which we call spine digraphs. Those are the digraphs D whose vertex set can be partitioned into two sets X and Y such that the subdigraph induced by X is traceable and Y is a stable set. We also show that Linial's Conjecture holds for spine digraphs.

preprint2013arXiv

A Faster Algorithm for Packing Branchings in Digraphs

We consider the problem of finding an integral packing of branchings in a capacitated digraph with root-set demands. Schrijver described an algorithm that returns a packing with at most m+n^3+r branchings that makes at most m(m+n^3+r) calls to an oracle that basically computes a minimum cut, where n is the number of vertices, m is the number of arcs and r is the number of root-sets of the input digraph. In this work we provide an algorithm, inspired on ideas of Schrijver and on an paper of Gabow and Manu, that returns a packing with at most m+r-1 branchings and makes at most 2n+m+r-1 oracle calls.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Orlando Lee

Research overview

Is this your work?

4 publications

A family of counterexamples for a conjecture of Berge on $α$ -diperfect digraphs

Facility Leasing with Penalties

On Linial's Conjecture for Spine Digraphs

A Faster Algorithm for Packing Branchings in Digraphs

See the researcher in context

Building this map preview

Orlando Lee

Research overview

Is this your work?

4 publications

A family of counterexamples for a conjecture of Berge on ααα-diperfect digraphs

Facility Leasing with Penalties

On Linial's Conjecture for Spine Digraphs

A Faster Algorithm for Packing Branchings in Digraphs

See the researcher in context

Building this map preview

A family of counterexamples for a conjecture of Berge on $α$ -diperfect digraphs