COMBINATORICS FOR COMPUTER SCIENCE
CONTENTS GRAPH ALGORITHMS I MINING PRESERVING STRUCTURES IN A GRAPH SEQUENCE 3 ON THE MOST IMBALANCED ORIENTATION OF A GRAPH 16 CHEEGER INEQUALITIES FOR GENERAL EDGE WEIGHTED DIRECTED GRAPHS 30 GAME THEORY AND ALGORITHMS STRATEGY PROOF MECHANISM FOR OBNOXIOUS FACILITY LOCATION ON A LINE 45 BIN PACKING GAME WITH AN INTEREST MATRIX 57 THE LEAST CORE AND NUCLEOLUS OF PATH COOPERATIVE GAMES 70 REVERSIBLE PEBBLE GAME ON TREES 83 COMPUTATIONAL COMPLEXITY COMBINATIONS OF SOME SHOP SCHEDULING PROBLEMS AND THE SHORTEST PATH PROBLEM COMPLEXITY AND APPROXIMATION ALGORITHMS 97 COMPLEXITY OF GRUNDY COLORING AND ITS VARIANTS 109 ON THE COMPLEXITY OF THE MINIMUM INDEPENDENT SET PARTITION PROBLEM 121 BIVARIATE COMPLEXITY ANALYSIS OF ALMOST FOREST DELETION 133 1 43 96 APPROXIMATION ALGORITHMS IMPROVED APPROXIMATION ALGORITHMS FOR MIN MAX AND MINIMUM VEHICLE ROUTING PROBLEMS 147 IMPROVED APPROXIMATION ALGORITHMS FOR THE MAXIMUM HAPPY VERTICES AND EDGES PROBLEMS 159 AN APPROXIMATION ALGORITHM FOR THE SMALLEST COLOR SPANNING CIRCLE PROBLEM 171 APPROXIMATION ALGORITHMS FOR THE CONNECTED SENSOR COVER PROBLEM 183 CIRCUITS ALGORITHMS SKEW CIRCUITS OF SMALL WIDTH 199 CORRELATION BOUNDS AND SAT ALGORITHMS FOR SMALL LINEAR SIZE CIRCUITS 211 COMMUTING QUANTUM CIRCUITS WITH FEW OUTPUTS ARE UNLIKELY TO BE CLASSICALLY SIMULATABLE 223 EVALUATING MATRIX CIRCUITS 235 COMPUTING AND GRAPH APPROXIMATION AND NONAPPROXIMABILITY FOR THE ONE SIDED SCAFFOLD FILLING PROBLEM 251 PACKING CUBES INTO A CUBE IN D 3 DIMENSIONS 264 TOWARDS FLEXIBLE DEMANDS IN ONLINE LEASING PROBLEMS 277 LOWER BOUNDS FOR THE SIZE OF NONDETERMINISTIC CIRCUITS 289 145 198 250 COMPUTING MINIMUM DILATION SPANNING TREES IN GEOMETRIC GRAPHS 297 SPEEDY COLORFUL SUBTREES 310 GRAPH ALGORITHMS II ALGORITHMIC ASPECTS OF DISJUNCTIVE DOMINATION IN GRAPHS 325 ALGORITHMIC ASPECT OF MINUS DOMINATION ON SMALL DEGREE GRAPHS 337 TIME SPACE TRADEOFFS FOR DYNAMIC PROGRAMMING ALGORITHMS IN TREES AND BOUNDED TREEWIDTH GRAPHS 349 REDUCING RANK OF THE ADJACENCY MATRIX BY GRAPH MODIFICATION 361 KNAPSACK AND ALLOCATION ON THE NUMBER OF ANCHORED RECTANGLE PACKINGS FOR A PLANAR POINT SET 377 APPROXIMATE TRUTHFUL MECHANISM DESIGN FOR TWO DIMENSIONAL ORTHOGONAL KNAPSACK PROBLEM 390 ONLINE INTEGRATED ALLOCATION OF BERTHS AND QUAY CRANES IN CONTAINER TERMINALS WITH 1 LOOKAHEAD 402 DISJOINT PATH ALLOCATION WITH SUBLINEAR ADVICE 417 GRAPH ALGORITHMS III DYNAMIC TREE SHORTCUT WITH CONSTANT DEGREE 433 324 375 THE RECTILINEAR STEINER TREE PROBLEM WITH GIVEN TOPOLOGY AND LENGTH RESTRICTIONS 445 COMPACT MONOTONE DRAWING OF TREES 457 A MEASURE AND CONQUER APPROACH FOR THE PARAMETERIZED BOUNDED DEGREE ONE VERTEX DELETION 469 RANDOM SAMPLING IN SPACE RESTRICTED SETTINGS 483 ENTROPY OF WEIGHT DISTRIBUTIONS OF SMALL BIAS SPACES AND PSEUDOBINOMIALITY 495 OPTIMAL ALGORITHMS FOR RUNNING MAX AND MIN FILTERS ON RANDOM INPUTS 507 MODEL CHECKING MSVL PROGRAMS BASED ON DYNAMIC SYMBOLIC EXECUTION 521 GEOMETRIC COVER ON THE COMPLETE WIDTH AND EDGE CLIQUE COVER PROBLEMS 537 UNIQUE COVERING PROBLEMS WITH GEOMETRIC SETS 548 LINEAR TIME APPROXIMATION SCHEMES FOR GEOMETRIC MAXIMUM COVERAGE 559 481 536 GRAPH ALGORITHMS I 1