Journal: Discrete Applied Mathematics

Found 533 papers in total
Rooted routing in the plane
Rooted routing in the plane
1995,
This paper, which was published without an abstract, is concerned with the following...
Weighted finite transducers in image processing
Weighted finite transducers in image processing
1995,
Culik and Karhumäki studied weighted finite automata (WFA) as devices computing...
Weighted fractional and integral k-matching in hypergraphs
Weighted fractional and integral k-matching in hypergraphs
1995,
The authors consider the problem of finding polynomial-time approximations of maximal...
A framework for adaptive sorting
A framework for adaptive sorting
1995,
A sorting algorithm is adaptive if it sorts sequences that are close to sorted faster...
Generating hard and diverse test sets for NP-hard graph problems
Generating hard and diverse test sets for NP-hard graph problems
1995,
In evaluating the performance of approximation algorithms for NP-hard problems, it is...
A study of the cyclic scheduling problem on parallel processors
A study of the cyclic scheduling problem on parallel processors
1995,
The authors address the problem of scheduling a set of generic tasks to be perfromed...
Alternating paths in edge-colored complete graphs
Alternating paths in edge-colored complete graphs
1995,
In an edge-colored graph, the paper says that a path is alternating if it has at least...
The complexities of the coefficients of the Tutte polynomial
The complexities of the coefficients of the Tutte polynomial
1995,
The complexity of calculating the coefficients of the Tutte polynomial of a graph is...
The complexity of harmonious colouring for trees
The complexity of harmonious colouring for trees
1995,
A harmonious colouring of a simple graph G is a proper vertex colouring such that each...
The set of super-stable marriages forms a distributive lattice
The set of super-stable marriages forms a distributive lattice
1995,
Relaxing the total orders of the preference lists of an instance of the stable...
Short encodings of planar graphs and maps
Short encodings of planar graphs and maps
1995,
The authors discuss space-efficient encoding schemes for planar graphs and maps. The...
Expected complexity of graph partitioning problems
Expected complexity of graph partitioning problems
1995,
The paper studies the expected time complexity of two graph partitioning problems: the...
Graphs with most number of three point induced connected subgraphs
Graphs with most number of three point induced connected subgraphs
1995,
Let G be a simple graph with e perfectly reliable edges and n nodes which fail...
On determining non-isotopic configurations of points on a circle
On determining non-isotopic configurations of points on a circle
1995,
Given a set P of 2 n colored points on a circle O, a configuration of P is a set...
A generalization of the stable matching problem
A generalization of the stable matching problem
1995,
It is known that there may not exist any stable matching for a given instance of the...
A unified approach to the first derivatives of graph polynomials
A unified approach to the first derivatives of graph polynomials
1995,
A general graph polynomial is introduced. It is proved that . Special cases of this...
Large (d,D,D',s)-bipartite digraphs
Large (d,D,D',s)-bipartite digraphs
1995,
A ( d,D,D',s)- digraph is a directed graph with diameter D and maximum out-degree d...
Approximation techniques for hypergraph partitioning problems
Approximation techniques for hypergraph partitioning problems
1995,
Techniques for approximating a hypergraph by a weighted graph for use in node...
The Shields-Harary number for wheel and broken wheel graphs
The Shields-Harary number for wheel and broken wheel graphs
1995,
The Shields-Harary number ( SH) is a graph parameter which has been interpreted in...
The NP-completeness of finding A-trials in Eulerian graphs and of finding spanning trees in hypergraphs
The NP-completeness of finding A-trials in Eulerian graphs and of finding spanning trees in hypergraphs
1995,
Samuel W. Bent and Udi Manber have shown that it is NP-complete to decide whether a...
A Monge property for the d-dimensional transportation problem
A Monge property for the d-dimensional transportation problem
1995,
In 1963, Hopman gave necessary and sufficient conditions under which a family of O(...
On the k-coloring of intervals
On the k-coloring of intervals
1995,
The problem of coloring a set of n intervals (from the real line) with a set of k...
Distances between traveling salesman tours
Distances between traveling salesman tours
1995,
Two metrics, based respectively on k- OPT and 2-OPT, for measuring the distance...
Optimal match-up strategies in stochastic scheduling
Optimal match-up strategies in stochastic scheduling
1995,
Practical scheduling problems require the consideration of random events that may...
Papers per page: