Journal: Discrete Applied Mathematics

Found 533 papers in total
Some concepts of stability analysis in combinatorial optimization
Some concepts of stability analysis in combinatorial optimization
1995,
This paper surveys the recent results in stability analysis for discrete optimization...
Optimal computation of census functions in the postal model
Optimal computation of census functions in the postal model
1995,
The authors consider the problem of computing a census function among n processors in...
A polynomial algorithm for an open shop problem with unit processing times and tree constraints
A polynomial algorithm for an open shop problem with unit processing times and tree constraints
1995,
In this paper the authors consider the optn shop problem with unit processing times...
Recognizing renamable generalized propositional Horn formulas is NP-complete
Recognizing renamable generalized propositional Horn formulas is NP-complete
1995,
Yamasaki and Doshita (1983) have defined an extension of the class of propositional...
Generating lower bounds for the linear arrangement problem
Generating lower bounds for the linear arrangement problem
1995,
The linear arrangement problem is a fundamental problem that arises in many practical...
Optimal separable partitioning in the plane
Optimal separable partitioning in the plane
1995,
Sets of points are called a separable if their convex hulls are disjoint. The authors...
NP-hardness of shop-scheduling problems with three jobs
NP-hardness of shop-scheduling problems with three jobs
1995,
This paper deals with the problem of scheduling n jobs on m machines in order to...
A combinatorial approach to the problem of self-assembly
A combinatorial approach to the problem of self-assembly
1995,
A formal scheme is proposed in order to mathematically describe some real features of...
Almost fully-parallel parentheses matching
Almost fully-parallel parentheses matching
1995,
The parentheses matching problem is considered. Suppose the authors are given a...
Efficient parallel recognition algorithms of cographs and distance hereditary graphs
Efficient parallel recognition algorithms of cographs and distance hereditary graphs
1995,
A parallel algorithm to recognize cographs with a linear processor bound and a log 2 n...
Using local adaptations to reconfigure a spanning tree of a network
Using local adaptations to reconfigure a spanning tree of a network
1995,
The paper defines the notion of a local adaptation of a spanning tree in a biconnected...
The Hamiltonicity of directed σ-τ Cayley graphs (Or: A tale of backtracking)
The Hamiltonicity of directed σ-τ Cayley graphs (Or: A tale of backtracking)
1995,
Let τ be the 2-cycle (12) and σ the n- cycle (12ëëë n). These...
Covering with latin transversals
Covering with latin transversals
1995,
Given an n×n matrix A=[a ij ], a transversal of A is a set of elements, one from...
The permutahedron of series-parallel posets
The permutahedron of series-parallel posets
1995,
The permutahedron Perm(P) of a poset P is defined as the convex hull of those...
L-polytopes and equiangular lines
L-polytopes and equiangular lines
1995,
A construction providing sets of equiangular lines from integral lattices is given....
Probing the arrangement of hyperplanes
Probing the arrangement of hyperplanes
1995,
This paper investigates the combinatorial complexity of an algorithm to determine the...
Probabilities within optimal strategies for tournament games
Probabilities within optimal strategies for tournament games
1995,
Let T be a tournament. The tournament game on T is: Two players independently pick a...
Solution of the knight’s Hamiltonian path problem on chessboards
Solution of the knight’s Hamiltonian path problem on chessboards
1994,
Is it possible for a knight to visit all squares of an n×n chessboard on an...
Edge-disjoint packings of graphs
Edge-disjoint packings of graphs
1994,
In this paper the authors study two types of edge-disjoint packings of graphs. The...
Guarding rectangular art galleries
Guarding rectangular art galleries
1994,
Consider a rectangular art gallery divided into n rectangular rooms, such that any two...
A discrete model for studying existence and uniqueness of solutions in nonlinear resistive circuits
A discrete model for studying existence and uniqueness of solutions in nonlinear resistive circuits
1994,
Two combinatorial problems raised by the fundamental question of the existence and...
More facets from fences for linear ordering and acyclic subgraph polytopes
More facets from fences for linear ordering and acyclic subgraph polytopes
1994,
The authors present new facets for the linear ordering polytope. These new facets...
On Halin subgraphs and supergraphs
On Halin subgraphs and supergraphs
1995,
In this paper, the authors present two complexity results. The first pertains to the...
Clique covering and clique partition in generalizations of line graphs
Clique covering and clique partition in generalizations of line graphs
1995,
Cliques are complete subgraphs of a graph. This note shows that minimum sets of...
Papers per page: