Journal: Discrete Applied Mathematics
Approximation algorithms for some optimum communication spanning tree problems
Wu Bang Ye
Let G =( V,E,w ) be an undirected graph with nonnegative edge length function w and...
Parallel machine scheduling with a common server
Hall Nicholas G.
This paper considers the nonpreemptive scheduling of a given set of jobs on several...
Asymptotically optimal erasure-resilient codes for large disk arrays
Colbourn Charles J.
Reliability is a major concern in the design of large disk arrays. Hellerstein et al ....
Computing Prüfer codes efficiently in parallel
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
Given a permutation graph G with its corresponding permutation π, we present an...
An introduction to cocyclic generalised Hadamard matrices
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
The paper considers the classic linear assignment problem with a min-sum objective...
Many-to-many matching: Stable polyandrous polygamy (or polygamous polyandry)
The major results known for the marriage and university admissions problems, the...
Envelopes and clutters
In this paper, a set function ϕ defined on a finite set Ω is said to be an...
A note on the generalized Steiner tree polytope
Salazar Juan Jos
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
Sherali Hanif D.
In this paper, we consider the reformulation–linearization technique (RLT) of...
Maximum packing for biconnected outerplanar graphs
The problem of determining the maximum number of vertex-disjoint subgraphs of a...
Chang Gerard J.
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
Fellows Michael R.
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
Rangan C. Pandu
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
Feedback vertex problems consist of removing a minimal number of vertices of a...
Maximal cubic graphs with diameter 4
We prove that there is no cubic graph with diameter 4 on 40 vertices. This implies...
Upper bounds to the clique width of graphs
Hierarchical decompositions of graphs are interesting for algorithmic purposes. Many...
Generic rigidity of molecular graphs via ear decomposition
A basic model in the study of structural rigidity is a network of rigid bars connected...
New results on induced matchings
Golumbic Martin Charles
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
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
A median of a k -tuble ≠ = (x 1 ,…,x k ) of vertices of a finite connected...
Computing orbit period in max–min algebra
Periodicity of vector orbits in max–min algebra is studied. It is proved that...
Sparse orthogonal matrices and the Haar wavelet
The sparsity of orthogonal matrices which have a column of nonzeros is studied. It is...
Papers per page: