Journal: Discrete Applied Mathematics

Found 533 papers in total
Approximation algorithms for some optimum communication spanning tree problems
Approximation algorithms for some optimum communication spanning tree problems
2000,
Let G =( V,E,w ) be an undirected graph with nonnegative edge length function w and...
Parallel machine scheduling with a common server
Parallel machine scheduling with a common server
2000,
This paper considers the nonpreemptive scheduling of a given set of jobs on several...
Asymptotically optimal erasure-resilient codes for large disk arrays
Asymptotically optimal erasure-resilient codes for large disk arrays
2000,
Reliability is a major concern in the design of large disk arrays. Hellerstein et al ....
Computing Prüfer codes efficiently in parallel
Computing Prüfer codes efficiently in parallel
2000,
A Prüfer code of a labeled free tree with n nodes is a sequence of length n...
An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
2000,
Given a permutation graph G with its corresponding permutation π, we present an...
An introduction to cocyclic generalised Hadamard matrices
An introduction to cocyclic generalised Hadamard matrices
2000,
Many codes and sequences designed for robust or secure communications are built from...
Algorithms and codes for dense assignment problems: The state of the art
Algorithms and codes for dense assignment problems: The state of the art
2000,
The paper considers the classic linear assignment problem with a min-sum objective...
Many-to-many matching: Stable polyandrous polygamy (or polygamous polyandry)
Many-to-many matching: Stable polyandrous polygamy (or polygamous polyandry)
2000,
The major results known for the marriage and university admissions problems, the...
Envelopes and clutters
Envelopes and clutters
2000,
In this paper, a set function ϕ defined on a finite set Ω is said to be an...
A note on the generalized Steiner tree polytope
A note on the generalized Steiner tree polytope
2000,
The generalized Steiner tree problem (GSTP) is a variant of the classical Steiner tree...
Reduced first-level representations via the reformulation–linearization technique: Results, counterexamples, and computations
Reduced first-level representations via the reformulation–linearization technique: Results, counterexamples, and computations
2000,
In this paper, we consider the reformulation–linearization technique (RLT) of...
Maximum packing for biconnected outerplanar graphs
Maximum packing for biconnected outerplanar graphs
2000,
The problem of determining the maximum number of vertex-disjoint subgraphs of a...
Pseudo-Hamiltonian-connected graphs
Pseudo-Hamiltonian-connected graphs
2000,
Given a graph G and a positive integer k , denote by G[k] the graph obtained from G by...
The complexity of irredundant sets parameterized by size
The complexity of irredundant sets parameterized by size
2000,
An irredundant set of vertices V′⊆V in a graph G=(V,E) has the property...
Algorithmic aspects of clique-transversal and clique-independent sets
Algorithmic aspects of clique-transversal and clique-independent sets
2000,
A minimum clique-transversal set MCT(G) of a graph G = (V,E) is a set S⊆V of...
Solving the feedback vertex set problem on undirected graphs
Solving the feedback vertex set problem on undirected graphs
2000,
Feedback vertex problems consist of removing a minimal number of vertices of a...
Maximal cubic graphs with diameter 4
Maximal cubic graphs with diameter 4
2000,
We prove that there is no cubic graph with diameter 4 on 40 vertices. This implies...
Upper bounds to the clique width of graphs
Upper bounds to the clique width of graphs
2000,
Hierarchical decompositions of graphs are interesting for algorithmic purposes. Many...
Generic rigidity of molecular graphs via ear decomposition
Generic rigidity of molecular graphs via ear decomposition
2000,
A basic model in the study of structural rigidity is a network of rigid bars connected...
New results on induced matchings
New results on induced matchings
2000,
A matching in a graph is a set of edges no two of which share a common vertex. A...
Straight line embeddings of rooted star forests in the plane
Straight line embeddings of rooted star forests in the plane
2000,
For every 1≤i≤n , let T i be a rooted star with root ν i is not necessarily...
The median function on median graphs and semilattices
The median function on median graphs and semilattices
2000,
A median of a k -tuble ≠ = (x 1 ,…,x k ) of vertices of a finite connected...
Computing orbit period in max–min algebra
Computing orbit period in max–min algebra
2000,
Periodicity of vector orbits in max–min algebra is studied. It is proved that...
Sparse orthogonal matrices and the Haar wavelet
Sparse orthogonal matrices and the Haar wavelet
2000,
The sparsity of orthogonal matrices which have a column of nonzeros is studied. It is...
Papers per page: