# Discrete Applied Mathematics

Discrete Applied Mathematics > 1996 > 71 > 1-3 > 153-169

^{l}

^{o}

^{g}

^{δ}

^{n}in polynomial time for any δ < 1, unless NP DTIME[2

^{p}

^{o}

^{l}

^{y}

^{l}

^{o}...

Discrete Applied Mathematics > 1997 > 72 > 1-2 > 71-84

Discrete Applied Mathematics > 1997 > 78 > 1-3 > 207-226

Discrete Applied Mathematics > 1997 > 80 > 2-3 > 251-254

Discrete Applied Mathematics > 1998 > 81 > 1-3 > 1-7

_{1}, ..., a

_{n}andt and are to determine if some subset of thea

_{i}sums tot. We investigate the boundary between easy and hard variations of this problem. In particular, we consider the cases where the sequencea

_{1}, ..., a

_{n}is an arithmetic progression, a chain or superincreasing and where thea...

Discrete Applied Mathematics > 1998 > 84 > 1-3 > 253-257

Discrete Applied Mathematics > 1998 > 85 > 1 > 59-70

Discrete Applied Mathematics > 1998 > 85 > 1 > 71-86

Discrete Applied Mathematics > 1998 > 87 > 1-3 > 269-274

_{c}

_{,}

_{r}be the integer hull of the intersection of the assignment polytope with a given hyperplane H = {x = (x

_{i}

_{j}) R

^{n}

^{x}

^{n}:

^{n}

_{i}

_{=}

_{1}

^{n}

_{j}

_{=}

_{1}c

_{i}

_{j}x

_{i}

_{j}= r}. We show that the problem of checking whether two given extreme points of Q

_{c}

_{,}

_{r}are nonadjacent on Q

_{c}...

Discrete Applied Mathematics > 1998 > 89 > 1-3 > 213-242

Discrete Applied Mathematics > 1999 > 91 > 1-3 > 251-263

Discrete Applied Mathematics > 1999 > 92 > 2-3 > 177-191

_{6}, triangle)-free, and (P

_{6}, C

_{4})-free. The algorithm devised for (P

_{6}, C

_{4})-free graphs is based on the search of simple augmenting trees and can be extended to heuristically solve the problem in a general graph.

Discrete Applied Mathematics > 1999 > 92 > 2-3 > 247-251

Discrete Applied Mathematics > 1999 > 96-97 > 337-362

Discrete Applied Mathematics > 2000 > 99 > 1-3 > 413-425

Discrete Applied Mathematics > 2000 > 102 > 3 > 175-188

Discrete Applied Mathematics > 2001 > 108 > 1-2 > 65-83

_{1}and v

_{2}, and attaches...

Discrete Applied Mathematics > 2001 > 108 > 3 > 325-328

Discrete Applied Mathematics > 2002 > 118 > 1-2 > 99-113

Discrete Applied Mathematics > 2002 > 119 > 1-2 > 117-128

^{2}) and domination number at least

_{k}

_{=}

_{0}

^{n}

^{-}

^{2}(k!). Extending this result, we show that by investing...