Journal: Discrete Applied Mathematics

Found 533 papers in total
Bipolar orientations revisited
Bipolar orientations revisited
1995,
Acyclic orientations with exactly one source and one sink-the so-called bipolar...
Hypercube embedding of generalized bipartite metrics
Hypercube embedding of generalized bipartite metrics
1995,
A metric d is h- embeddable if it can be isometrically embedded in some hypercube....
Polynomial invariants of graphs with state models
Polynomial invariants of graphs with state models
1995,
The authors reformulate a polynomial invariant of graphs defined by Negami, using the...
Universal covers of graphs: Isomorphism to depth n-1 implies isomorphism to all depths
Universal covers of graphs: Isomorphism to depth n-1 implies isomorphism to all depths
1995,
Vertex- and edge-labeled digraphs have been used to model computer networks, and the...
Compatible eulerian circuits in
Compatible eulerian circuits in
1995,
Let be the complete symmetric digraph with a loop at each vertex. The authors say that...
Joint performance of greedy heuristics for the integer knapsack problem
Joint performance of greedy heuristics for the integer knapsack problem
1995,
This paper analzyes the worst-case performance of combinations of greedy heuristics...
A lower bound of the expected maximum number of edge-disjoint s-t paths on probabilistic graphs
A lower bound of the expected maximum number of edge-disjoint s-t paths on probabilistic graphs
1995,
For a probabilistic graph , where G is an undirected graph with specified source...
On the channel capacity of read/write isolated memory
On the channel capacity of read/write isolated memory
1995,
The paper applies graph theory to find upper and lower bounds on the channel capacity...
Half-integral flows in a planar graph with four holes
Half-integral flows in a planar graph with four holes
1995,
Suppose that s a planar graph embedded in the conclusion plane, that I, J, K, O are...
Clique tree inequalities define facets of the asymmetric traveling salesman polytope
Clique tree inequalities define facets of the asymmetric traveling salesman polytope
1995,
This paper solves, in the affermative, the open question of whether the...
The depth and width of local minima in discrete solution spaces
The depth and width of local minima in discrete solution spaces
1995,
Heuristic search techniques such as simulated annealing and tabu search require...
Finding all common bases in two matroids
Finding all common bases in two matroids
1995,
In this paper, the authors present an algorithm for finding all common bases in two...
Generating most parsimonious reconstructions on a tree: A genralization of the Farris-Swofford-Maddison method
Generating most parsimonious reconstructions on a tree: A genralization of the Farris-Swofford-Maddison method
1995,
A combinatorial optimization problem regarding the assignments (called...
Maximizing traveling salesman problem for special matrices
Maximizing traveling salesman problem for special matrices
1995,
The authors consider the maximizing travelling salesman problem (MTSP) for two special...
Modelling piecewise linear concave costs in a tree partitioning problem
Modelling piecewise linear concave costs in a tree partitioning problem
1994,
An important modelling question is that of how to obtain tight mixed integer...
Finding degeneracies among sets of lines
Finding degeneracies among sets of lines
1995,
Suppose there are k sets each containing n lines in the plane. One might be interested...
An algorithm for fractional assignment problems
An algorithm for fractional assignment problems
1995,
In this paper the authors propose a polynomial-time algorithm for fractional...
On the poset of all posets on n elements
On the poset of all posets on n elements
1994,
The authors consider the poset of all posets on n elements where the partial order is...
Hamiltonian circuits determining the order of chromosomes
Hamiltonian circuits determining the order of chromosomes
1994,
According to Bennett’s model of cytogenetics the spatial order in haploid...
On the complexity of the embedding problem for hypercube related graphs
On the complexity of the embedding problem for hypercube related graphs
1993,
The n- dimensional hypercube is the graph with 2 n nodes labelled 0,1,...,2’ n-1...
The allocation problem in hardware design
The allocation problem in hardware design
1993,
In the synthesis of hardware structures different design steps are solved by...
Neighborhood subtree tolerance graphs
Neighborhood subtree tolerance graphs
1993,
In this paper, the authors introduce neighborhood subtree tolerance (NeST) graphs...
Tree-width, path-width, and cutwidth
Tree-width, path-width, and cutwidth
1993,
Let tw( G), pw( G), c(G), ℝ (G) denote, respectively, the tree-width, path-width,...
Linear-time separation algorithms for the three-index assignment polytope
Linear-time separation algorithms for the three-index assignment polytope
1993,
Balas and Saltzman identified several classes of facet inducing inequalities for the...
Papers per page: