Journal: Discrete Optimization

Found 150 papers in total
Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem
Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem
2012,
In this note, we show that if the maximum clique problem can be solved by a polynomial...
A polyhedral study of lot‐sizing with supplier selection
A polyhedral study of lot‐sizing with supplier selection
2012,
The traditional lot‐sizing problem is to find the least cost production...
On dynamic monopolies of graphs: The average and strict majority thresholds
On dynamic monopolies of graphs: The average and strict majority thresholds
2012,
Let G be a graph and τ : V ( G ) → ‐ N ∪ { 0 } be an assignment of...
On inclusionwise maximal and maximum cardinality k‐clubs in graphs
On inclusionwise maximal and maximum cardinality k‐clubs in graphs
2012,
A k ‐club is a distance‐based graph‐theoretic generalization of a...
An algorithm for finding a maximum t‐matching excluding complete partite subgraphs
An algorithm for finding a maximum t‐matching excluding complete partite subgraphs
2012,
For an integer t and a fixed graph H , we consider the problem of finding a maximum t...
How tight is the corner relaxation? Insights gained from the stable set problem
How tight is the corner relaxation? Insights gained from the stable set problem
2012,
The corner relaxation of a mixed‐integer linear program is a central concept in...
On the bounds for the largest Laplacian eigenvalues of weighted graphs
On the bounds for the largest Laplacian eigenvalues of weighted graphs
2012,
We consider weighted graphs, such as graphs where the edge weights are positive...
Exact weighted vertex coloring via branch‐and‐price
Exact weighted vertex coloring via branch‐and‐price
2012,
We consider the Weighted Vertex Coloring Problem (WVCP), in which a positive weight is...
Coordination mechanisms with hybrid local policies
Coordination mechanisms with hybrid local policies
2011,
We study coordination mechanisms for scheduling n jobs on m parallel machines where...
Finding low cost TSP and 2‐matching solutions using certain half‐integer subtour vertices
Finding low cost TSP and 2‐matching solutions using certain half‐integer subtour vertices
2011,
Consider the traveling salesman problem (TSP) defined on the complete graph, where the...
A branch‐and‐cut algorithm for the minimum‐adjacency vertex coloring problem
A branch‐and‐cut algorithm for the minimum‐adjacency vertex coloring problem
2011,
In this work we study a particular way of dealing with interference in combinatorial...
Partial multicovering and the d‐consecutive ones property
Partial multicovering and the d‐consecutive ones property
2011,
We design approximation algorithms for multicovering problems. We focus on...
Courcelle’s theorem–A game‐theoretic approach
Courcelle’s theorem–A game‐theoretic approach
2011,
MSO‐definable problems can be solved in linear time on graphs of bounded...
Orbitopal fixing
Orbitopal fixing
2011,
The topic of this paper are integer programming models in which a subset of...
On compact k‐edge‐colorings: A polynomial time reduction from linear to cyclic
On compact k‐edge‐colorings: A polynomial time reduction from linear to cyclic
2011,
A k ‐edge‐coloring of a graph G = ( V , E ) is a function c that assigns...
Valid inequalities and branch‐and‐cut for the clique pricing problem
Valid inequalities and branch‐and‐cut for the clique pricing problem
2011,
Motivated by an application in highway pricing, we consider the problem that consists...
The Wiener maximum quadratic assignment problem
The Wiener maximum quadratic assignment problem
2011,
We investigate a special case of the maximum quadratic assignment problem where one...
On duality and fractionality of multicommodity flows in directed networks
On duality and fractionality of multicommodity flows in directed networks
2011,
In this paper we address a topological approach to multiflow (multicommodity flow)...
Two classes of Quadratic Assignment Problems that are solvable as Linear Assignment Problems
Two classes of Quadratic Assignment Problems that are solvable as Linear Assignment Problems
2011,
The Quadratic Assignment Problem is one of the hardest combinatorial optimization...
A Greedy Partition Lemma for directed domination
A Greedy Partition Lemma for directed domination
2011,
A directed dominating set in a directed graph D is a set S of vertices of V such that...
On the complexity of submodular function minimisation on diamonds
On the complexity of submodular function minimisation on diamonds
2011,
Let ( L ; ⊓ , ⊔ ) be a finite lattice and let n be a...
The maximum k‐colorable subgraph problem and orbitopes
The maximum k‐colorable subgraph problem and orbitopes
2011,
Given an undirected node‐weighted graph and a positive integer k , the maximum...
A proof of a conjecture on diameter 2‐critical graphs whose complements are claw‐free
A proof of a conjecture on diameter 2‐critical graphs whose complements are claw‐free
2011,
A graph G is diameter 2‐critical if its diameter is 2, and the deletion of any...
Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
2011,
Motivated by the need for succinct representations of all ‘small’...
Papers per page: