Journal: Discrete Applied Mathematics

Found 533 papers in total
Sensitivity analysis for knapsack problems: Another negative result
Sensitivity analysis for knapsack problems: Another negative result
1999,
We answer a question of Blair on the computational complexity of a problem related to...
Spectral partitioning with multiple eigenvectors
Spectral partitioning with multiple eigenvectors
1999,
The graph partitioning problem is to divide the vertices of a graph into disjoint...
Path optimization for graph partitioning problems
Path optimization for graph partitioning problems
1999,
This paper presents a new heuristic for graph partitioning called Path Optimization...
A fast and simple Steiner routing heuristic
A fast and simple Steiner routing heuristic
1999,
This paper presents a simple yet efficient heuristic for rectilinear Steiner routing....
Class Steiner trees and VLSI-design
Class Steiner trees and VLSI-design
1999,
We consider a generalized version of the Steiner problem in graphs, motivated by the...
A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis
A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis
1999,
A recently introduced graph-theoretic notion of signed hypergraph is studied. In...
Routing multiterminal nets on a hexagonal grid
Routing multiterminal nets on a hexagonal grid
1999,
Channel routing is a vital task in the layout design of VLSI circuits. Multiterminal...
Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
1999,
We study a group of clustering problems on bipartite and chordal graphs. Our objective...
Minimal connected enclosures on an embedded planar graph
Minimal connected enclosures on an embedded planar graph
1999,
We study five problems of finding minimal enclosures comprised of elements of a...
The b-chromatic number of a graph
The b-chromatic number of a graph
1999,
The achromatic number ψ( G ) of a graph G =( V,E ) is the maximum k such that V...
Generalized partitions of graphs
Generalized partitions of graphs
1999,
A general graph partitioning problem, which includes graph colouring, homomorphism to...
On the algorithmic complexity of twelve covering and independence parameters of graphs
On the algorithmic complexity of twelve covering and independence parameters of graphs
1999,
The definitions of four previously studied parameters related to total coverings and...
Compatible Hamilton decompositions of directed wrapped butterfly graphs
Compatible Hamilton decompositions of directed wrapped butterfly graphs
1999,
In this article we prove a conjecture of Bermond, Darrot, Delmas, and Perennes by...
Construction of a simple elimination scheme for a chordal comparability graph in linear time
Construction of a simple elimination scheme for a chordal comparability graph in linear time
1999,
We describe a linear-time algorithm to build a simple elimination scheme for a chordal...
Even and odd pairs in comparability and in P4-comparability graphs
Even and odd pairs in comparability and in P4-comparability graphs
1999,
We characterize even and odd pairs in comparability and in P 4 -comparability graphs....
A note on graphs with large girth and small minus domination number
A note on graphs with large girth and small minus domination number
1999,
Dunbar et al. introduced the minus domination number γ – ( G ) of a graph...
Optimal binary trees with order constraints
Optimal binary trees with order constraints
1999,
Given a sequence of numbers a 1 , ..., a q , find a binary tree with q leaves...
Bipartite embeddings of trees in the plane
Bipartite embeddings of trees in the plane
1999,
In this paper we consider the following embedding problem. A point set P in the plane...
Matrices with maximum exponents in the class of doubly stochastic primitive matrices
Matrices with maximum exponents in the class of doubly stochastic primitive matrices
1999,
We characterize those doubly stochastic, primitive matrices for which the bounds for...
Transistor chaining in static CMOS functional cells of arbitrary planar topology
Transistor chaining in static CMOS functional cells of arbitrary planar topology
1999,
A technique for chaining the transistors in the layouts of static complementary metal...
Minimizing broadcast costs under edge reductions in tree networks
Minimizing broadcast costs under edge reductions in tree networks
1999,
We study the broadcasting of messages in tree networks under edge reductions. When an...
Approximating the weight of shallow Steiner trees
Approximating the weight of shallow Steiner trees
1999,
This paper deals with the problem of constructing Steiner trees of minimum weight with...
PlaNet – a software package of algorithms and heuristics for disjoint paths in Planar Networks
PlaNet – a software package of algorithms and heuristics for disjoint paths in Planar Networks
1999,
We present a package for algorithms on planar networks. This package comes with a...
Compound construction of broadcast networks
Compound construction of broadcast networks
1999,
Compound methods have been shown to be very effective in the construction of broadcast...
Papers per page: