@article{Andreae-Bandelt/95,
AUTHOR = {Andreae, Thomas and Bandelt, Hans-J{\"u}rgen},
TITLE = {Performance guarantees for approximation algorithms depending on parametrized triangle inequalities},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {1-16},
YEAR = {1995, February},
KEYWORDS = {approximation algorithm, performance guarantee, parametrized triangle inequality, traveling salesman problem, Steiner tree, anticlustering},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bouchet-Cunningham/95,
AUTHOR = {Bouchet, Andr{\'e} and Cunningham, William H.},
TITLE = {Delta-matroids, jump systems, and bisubmodular polyhedra},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {17-32},
YEAR = {1995, February},
KEYWORDS = {delta-matroid, jump system, bisubmodular polyhedron, composition theorem},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Carlson-Chen-Meliksetian/95,
AUTHOR = {Carlson, Bradley S. and Chen, C.Y. Roger and Meliksetian, Dikran S.},
TITLE = {Dual Eulerian properties of plane multigraphs},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {33-50},
YEAR = {1995, February},
KEYWORDS = {Eulerian graphs, planar graphs, VLSI layout},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hofmeister/95,
AUTHOR = {Hofmeister, M.},
TITLE = {Enumeration of concrete regular covering projections},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {51-61},
YEAR = {1995, February},
KEYWORDS = {graph covering, enumeration, voltage group, subgroup lattice},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jia/95,
AUTHOR = {Jia, Xing-De},
TITLE = {Extremal Cayley digraphs of finite cyclic groups},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {62-75},
YEAR = {1995, February},
KEYWORDS = {Cayley digraphs, average distance, explicit construction, extremal problems},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Karchmer-Kushilevitz-Nisan/95,
AUTHOR = {Karchmer, Mauricio and Kushilevitz, Eyal and Nisan, Noam},
TITLE = {Fractional covers and communication complexity},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {76-92},
YEAR = {1995, February},
KEYWORDS = {communication complexity, linear programming bound},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kushilevitz-Mansour-Rabin/95,
AUTHOR = {Kushilevitz, Eyal and Mansour, Yishay and Rabin, Michael O.},
TITLE = {On lotteries with unique winners},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {93-98},
YEAR = {1995, February},
KEYWORDS = {lotteries, lower bounds, symmetry breaking},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lin-Skiena/95,
AUTHOR = {Lin, Yaw-Ling and Skiena, Steven S.},
TITLE = {Algorithms for square roots of graphs},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {99-118},
YEAR = {1995, February},
KEYWORDS = {square graphs, power graphs, tree square, planar square graphs},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lovasz-Naor-Newman-Wigderson/95,
AUTHOR = {Lov{\'a}sz, L{\'a}szl{\'o} and Naor, Moni and Newman, Ilan and Wigderson, Avi},
TITLE = {Search problems in the decision tree model},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {119-132},
YEAR = {1995, February},
KEYWORDS = {boolean functions, decision trees},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Sherali-Lee/95,
AUTHOR = {Sherali, Hanif D. and Lee, Youngho},
TITLE = {Sequential and simultaneous liftings of minimal cover inequalities for generalized upper bound constrained knapsack polytopes},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {1},
PAGES = {133-153},
YEAR = {1995, February},
KEYWORDS = {GUB knapsack polytope, minimal GUB covers, reformulation-linearization technique, lifting, facets},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bang-Jensen-Frank-Jackson/95,
AUTHOR = {Bang-Jensen, J{\o}rgen and Frank, Andr{\'a}s and Jackson, Bill},
TITLE = {Preserving and increasing local edge-connectivity in mixed graphs},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {155-178},
YEAR = {1995},
KEYWORDS = {mixed graphs, splitting theorems, edge-connectivity, augmentation, branchings, network synthesis},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Fraughnaugh-Lundgren-Merz-Maybee-Pullman/95,
AUTHOR = {Fraughnaugh, Kathryn F. and Lundgren, J. Richard and Merz, Sarah K. and Maybee, John S. and Pullman, Norman J.},
TITLE = {Competition graphs of strongly connected and Hamiltonian digraphs},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {179-185},
YEAR = {1995},
KEYWORDS = {competition graph, conflict graph, strongly connected digraph, Hamiltonian digraph, communication network, edge clique cover, chordal graph, interval graph, cycle, inset},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gonzalez-Landaeta/95,
AUTHOR = {Gonz{\'a}lez, Jaime and Landaeta, Osvaldo},
TITLE = {A competitive strong spanning tree algorithm for the maximum bipartite matching problem},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {186-195},
YEAR = {1995},
KEYWORDS = {bipartite graphs, maximum matching, augmenting paths, strong spanning trees},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hamalainen-Honkala-Litsyn-ostergard/95,
AUTHOR = {H{\"a}m{\"a}l{\"a}inen, Heikki O. and Honkala, Iiro S. and Litsyn, Simon N. and {\"o}sterg{\AA}rd, Patric R.J.},
TITLE = {Bounds for binary codes that are multiple coverings of the farthest-off points},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {196-207},
YEAR = {1995},
KEYWORDS = {binary code, covering radius, multiple covering, football pool problem},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hell-Zhu/95,
AUTHOR = {Hell, Pavol and Zhu, Xuding},
TITLE = {The existence of homomorphisms to oriented cycles},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {208-222},
YEAR = {1995},
KEYWORDS = {graph homomorphisms, oriented cycles, homomorphism duality},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Schmidt-Siegel-Srinivasan/95,
AUTHOR = {Schmidt, Jeanette P. and Siegel, Alan and Srinivasan, Aravind},
TITLE = {Chernoff-Hoeffding bounds for applications with limited independence},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {223-250},
YEAR = {1995},
KEYWORDS = {Chernoff-Hoeffding bounds, large deviations, randomized algorithms, derandomization, limited independence, correlation inequalities, deterministic simulation},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Spinrad/95,
AUTHOR = {Spinrad, Jeremy P.},
TITLE = {Nonredundant 1's in $\Gamma$-free matrices},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {251-257},
YEAR = {1995},
KEYWORDS = {chordal bipartite graphs, totally balanced matrices, strongly chordal graphs, $\beta$-acyclic hypergraphs},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Yeap-Sarrafzadeh/95,
AUTHOR = {Yeap, Gary K.H. and Sarrafzadeh, Majid},
TITLE = {Sliceable floorplanning by graph dualization},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {258-280},
YEAR = {1995},
KEYWORDS = {very large scale integration (VLSI) floorplanning, sliceable floorplans, planar graphs, graph dualization},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Knuth/95,
AUTHOR = {Knuth, Donald E.},
TITLE = {Two-way rounding},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {281-290},
YEAR = {1995},
KEYWORDS = {rounding, partial sums, network flows, discrepancy},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Liestman-Shermer/95,
AUTHOR = {Liestman, Arthur L. and Shermer, Thomas C.},
TITLE = {Degree-constrained network spanners with nonconstant delay},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {291-321},
YEAR = {1995},
KEYWORDS = {grid, pyramid, X-tree, spanner, parallel network},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pippenger/95,
AUTHOR = {Pippenger, Nicholas},
TITLE = {Analysis of a recurrence arising from a construction for nonblocking networks},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {2},
PAGES = {322-345},
YEAR = {1995},
KEYWORDS = {asymptotic analysis, recurrence relation},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Barnes/95,
AUTHOR = {Barnes, Earl R.},
TITLE = {An inequality for probability moments with applications},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {3},
PAGES = {347-358},
YEAR = {1995},
KEYWORDS = {probabilities, inequalities, eigenvalues, moments},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cai-Corneil/95a,
AUTHOR = {Cai, Leizhen and Corneil, Derek G.},
TITLE = {Tree spanners},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {3},
PAGES = {359-387},
YEAR = {1995},
KEYWORDS = {graph algorithm, NP-complete, tree spanner, spanning tree, distance},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Franzblau/95,
AUTHOR = {Franzblau, D.S.},
TITLE = {Combinatorial algorithm for a lower bound on frame rigidity},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {3},
PAGES = {388-400},
YEAR = {1995},
KEYWORDS = {rigidity, degrees of freedom, frame, framework, network, graph, algorithm, ear decomposition, amorphous solid, glass, zero-frequency mode, dynamical matrix},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kortsarz-Peleg/95,
AUTHOR = {Kortsarz, Guy and Peleg, David},
TITLE = {Approximation algorithms for minimum-time broadcast},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {3},
PAGES = {401-427},
YEAR = {1995},
KEYWORDS = {broadcast, approximation},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Alonso-Reingold-Schott/95,
AUTHOR = {Alonso, Laurent and Reingold, Edward M. and Schott, Ren{\'e}},
TITLE = {Multidimensional divide-and-conquer maximin recurrences},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {3},
PAGES = {428-447},
YEAR = {1995},
KEYWORDS = {recurrence relations, divide and conquer, algorithmic analysis, partition trees},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jamison-Olariu/95a,
AUTHOR = {Jamison, Beverly and Olariu, Stephan},
TITLE = {P-components and the homogeneous decomposition of graphs},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {3},
PAGES = {448-463},
YEAR = {1995},
KEYWORDS = {graph decomposition, p-connectedness, graph algorithms, structured graph theory},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pitassi-Urquhart/95,
AUTHOR = {Pitassi, Toniann and Urquhart, Alasdair},
TITLE = {The complexity of the Haj{\'o}s calculus},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {3},
PAGES = {464-483},
YEAR = {1995},
KEYWORDS = {graph constructions, complexity of propositional proof systems, 3-colorability},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kierstead-Penrice-Trotter/95,
AUTHOR = {Kierstead, Henry A. and Penrice, Stephen G. and Trotter, William T.},
TITLE = {On-line and first-fit colouring of graphs that do not induce $P_5$},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {485-498},
YEAR = {1995},
KEYWORDS = {on-line algorithm, graph coloring, greedy algorithm},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Whittlesey-Georges-Mauro/95,
AUTHOR = {Whittlesey, Marshall A. and Georges, John P. and Mauro, David W.},
TITLE = {On the $\lambda$-number of $Q_n$ and related graphs},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {499-506},
YEAR = {1995},
KEYWORDS = {$\lambda$-labeling, $n$-cube, vertex labeling},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{McMorris-Powers/95,
AUTHOR = {McMorris, F.R. and Powers, R.C.},
TITLE = {The median procedure in a formal theory of consensus},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {507-516},
YEAR = {1995},
KEYWORDS = {consensus, median, semilattice},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bandelt-Steel/95,
AUTHOR = {Bandelt, Hans-J{\"u}rgen and Steel, Michael Anthony},
TITLE = {Symmetric matrices representable by weighted trees over a cancellative abelian monoid},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {517-525},
YEAR = {1995},
KEYWORDS = {trees, 4-point condition, abelian monoid, distance-hereditary graph},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Althofer-Leader/95,
AUTHOR = {Alth{\"o}fer, Ingo and Leader, Imre},
TITLE = {Correlation of boolean functions and pathology in recursion trees},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {526-535},
YEAR = {1995},
KEYWORDS = {tree search, reliable computing, correlation inequalities, game trees},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Newman-Wigderson/95,
AUTHOR = {Newman, Ilan and Wigderson, Avi},
TITLE = {Lower bounds on formula size of boolean functions using hypergraph entropy},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {536-542},
YEAR = {1995},
KEYWORDS = {boolean functions, graph entropy, circuit complexity},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Greenberg-Shih/95,
AUTHOR = {Greenberg, Ronald I. and Shih, Jau-Der},
TITLE = {Feasible offset and optimal offset for general single-layer channel routing},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {543-554},
YEAR = {1995},
KEYWORDS = {VLSI layout, channel routing, single-layer wire routing, discrete convolution, combinatorial algorithms},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ashley-Marcus/95,
AUTHOR = {Ashley, Jonathan and Marcus, Brian},
TITLE = {Canonical encoders for sliding block decoders},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {555-605},
YEAR = {1995},
KEYWORDS = {sliding block code, state splitting, symbolic dynamics},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bodlaender-Kloks-Kratsch/95,
AUTHOR = {Bodlaender, Hans L. and Kloks, Ton and Kratsch, Dieter},
TITLE = {Treewidth and pathwidth of permutation graphs},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {606-616},
YEAR = {1995},
KEYWORDS = {permutation graphs, graph algorithms, treewidth},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bhatt-Chung-Leighton-Rosenberg/95,
AUTHOR = {Bhatt, Sandeep N. and Chung, Fan R.K. and Leighton, Frank Thomson and Rosenberg, Arnold L.},
TITLE = {Salvage-embeddings of complete trees},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {617-637},
YEAR = {1995},
KEYWORDS = {synchronization networks, fault tolerance, congestion, dilation},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Klawe-Mumey/95,
AUTHOR = {Klawe, Maria and Mumey, Brendan},
TITLE = {Upper and lower bounds on constructing alphabetic binary trees},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {638-651},
YEAR = {1995},
KEYWORDS = {alphabetic binary trees, data structures, algorithms},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jevtic/95,
AUTHOR = {Jevti{\'c}, Du{\v{s}}an B.},
TITLE = {On families of sets of integral vectors whose representatives form sum-distinct sets},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {652-660},
YEAR = {1995},
KEYWORDS = {subset-sum, uniquely decodable, residual matrix, detecting matrix},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Krishnamurti-Narahari/95,
AUTHOR = {Krishnamurti, Ramesh and Narahari, Bhagirath},
TITLE = {An approximation algorithm for preemptive scheduling on parallel-task systems},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {661-669},
YEAR = {1995},
KEYWORDS = {parallel-task system, preemptive scheduling, schedule length, polynomial time, approximation algorithm},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bokowski-Schuchert/95,
AUTHOR = {Bokowski, J{\"u}rgen and Schuchert, Peter},
TITLE = {Altshuler's sphere $M^9_{963}$ revisited},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {670-677},
YEAR = {1995},
KEYWORDS = {oriented matroid, matroid polytope, polarity},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Snyder-Steele/95a,
AUTHOR = {Snyder, Timothy Law and Steele, Michael},
TITLE = {Equidistribution in all dimensions of worst-case point sets for the traveling salesman problem},
JOURNAL = {SIAM J. Disc.~Math.},
VOLUME = {8},
NUMBER = {4},
PAGES = {678-683},
YEAR = {1995},
KEYWORDS = {equidistribution, worst-case, nonlinear growth, traveling salesman, rectilinear Steiner tree, minimum spanning tree, minimum-weight matching},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}