Journal: Discrete Applied Mathematics

Found 533 papers in total
General vertex disjoint paths in series-parallel graphs
1993,
Let G=(V,E) be an undirected graph and let ( s i ,t i ), 1•i•k be k pairs of...
Optimal multiple interval assignments in frequency assignment and traffic phasing
1992,
The paper considers the optimal assignments of unions of intervals to the vertices of...
Probability of diameter two for Steinhaus graphs
1993,
A Steinhaus graph is a graph with n vertices whose adjacency matrix satisfies the...
Algorithms for routing around a rectangle
1992,
Simple efficient algorithms are given for three routing problems around a rectangle....
Characterizations of max-balanced flows
1992,
Let G=(V,A) be a graph with vertex set V and arc set a. A flow for G is an arbitrary...
Recognizing hidden bicircular networks
1993,
In this and a subsequent paper, the authors introduce a polynomial-time algorithm for...
Generalization of a theorem on the parametric maximum flow problem
1993,
A general theorem on the nesting property of minimum cuts in a parametric network and...
Birthday paradox, coupon collectors, caching algorithms and self-organizing search
1992,
This paper introduces a unified framework for the analysis of a class of random...
Openshop scheduling with machine dependent processing times
1992,
This paper examines the openshop problem with machine dependent processing times. Two...
A multiversion cautious scheduler with dynamic serialization constraints for database concurrency control
1992,
Let MC stand for a class of logs (i.e., sequences of read/write steps) that are...
On polynomial solvability of the high multiplicity total weighted tardiness problem
1993,
In a recent paper Hochbaum et al. developed a polynomial algorithm for solving a...
Minimum perfect bipartite matchings and spanning trees under categorization
1992,
Network optimization problems under categorization arise when the edge set is...
Some results on visibility graphs
1992,
A graph is a visibility graph if its vertices v 1 ,...,v n can be associated with...
Steiner’s problem in graphs: Heuristic methods
1992,
Real world problems arising in the layout of connection structures in networks as e.g....
The complexity of lifted inequalities for the knapsack problem
1992,
It is well known that one can obtain facets and valid inequalities for the knapsack...
Hamiltonian cycle is polynomial on cocomparability graphs
1992,
Finding a Hamiltonian path or a Hamiltonian cycle in a general graph are classic...
Processor interconnection networks from Cayley graphs
1992,
Cayley graphs of groups are presently being considered by the computer science...
Functional dependencies in relational databases: A lattice point of view
1992,
A lattice theoretic approach is developed to study the properties of functional...
Selective inheritance of attribute values in relational databases
1992,
Selective inheritance dependencies, or SIDs, are introduced to capture formally the...
Locking based on a pairwise decomposition of a transaction system
1992,
Locking is a synchronization primitive used in database systems to guarantee...
The number of keys in relational and nested relational databases
1992,
Combinatorial propositions, concerning the maximal number of minimal keys are...
Integer programming in VLSI design
1992,
This paper surveys some recent developments in the application of combinatorial...
Correlation in partially ordered sets
1992,
Correlation in partially ordered sets is a very active research area. The paper...
Some larger trivalent graphs having small diameters
1992,
This paper concerns an improvement of a result of Babai, Kantor and Lubotzky. It was...
Papers per page: