Journal: Journal of Combinatorial Optimization

Found 352 papers in total
Analysis and approximation for bank selection instruction minimization on partitioned memory architecture
Analysis and approximation for bank selection instruction minimization on partitioned memory architecture
2012,
A large number of embedded systems include 8‐bit microcontrollers for their...
Constraint bipartite vertex cover: simpler exact algorithms and implementations
Constraint bipartite vertex cover: simpler exact algorithms and implementations
2012,
Constraint bipartite vertex cover is a graph‐theoretical formalization of the...
The competition number of a graph with exactly two holes
The competition number of a graph with exactly two holes
2012,
Given an acyclic digraph D , the competition graph C ( D ) of D is the graph with the...
Independent dominating sets in triangle‐free graphs
Independent dominating sets in triangle‐free graphs
2012,
The independent domination number of a graph is the smallest cardinality of an...
Improving an exact approach for solving separable integer quadratic knapsack problems
Improving an exact approach for solving separable integer quadratic knapsack problems
2012,
We consider the specially structured (pure) integer Quadratic Multi‐Knapsack...
Combinatorial algorithms for the maximum k‐plex problem
Combinatorial algorithms for the maximum k‐plex problem
2012,
The maximum clique problem provides a classic framework for detecting cohesive...
Solving haplotype inference problem with non‐genotyped founders via integer linear programming
Solving haplotype inference problem with non‐genotyped founders via integer linear programming
2012,
In Cheng et al. (2009), the authors present a cubic time zero‐recombination...
A new approach to solve open‐partition problems
A new approach to solve open‐partition problems
2012,
A partition problem in one‐dimensional space is to seek a partition of a set of...
On backbone coloring of graphs
On backbone coloring of graphs
2012,
Let G be a graph and H a subgraph of G . A backbone‐ k ‐coloring of ( G...
The max quasi‐independent set problem
The max quasi‐independent set problem
2012,
In this paper, we deal with the problem of finding quasi‐independent sets in...
On the construction of k‐connected m‐dominating sets in wireless networks
On the construction of k‐connected m‐dominating sets in wireless networks
2012,
Connected dominating sets (CDS) that serve as a virtual backbone are now widely used...
Acyclic chromatic indices of planar graphs with girth at least five
Acyclic chromatic indices of planar graphs with girth at least five
2012,
An acyclic edge coloring of a graph G is a proper edge coloring such that no...
An improved time‐space lower bound for tautologies
An improved time‐space lower bound for tautologies
2011,
We show that for all reals c and d such that c 2 d <4 there exists a positive real...
Popular matchings: structure and algorithms
Popular matchings: structure and algorithms
2011,
An instance of the popular matching problem (POP-M) consists of a set of applicants...
Online tree node assignment with resource augmentation
Online tree node assignment with resource augmentation
2011,
Given a complete binary tree of height h , the online tree node assignment problem is...
On the performances of Nash equilibria in isolation games
On the performances of Nash equilibria in isolation games
2011,
We study the performances of Nash equilibria in isolation games, a class of...
A polynomial‐time perfect sampler for the Q‐Ising with a vertex‐independent noise
A polynomial‐time perfect sampler for the Q‐Ising with a vertex‐independent noise
2011,
We present a polynomial‐time perfect sampler for the Q ‐Ising with a...
Convex partitions with 2‐edge connected dual graphs
Convex partitions with 2‐edge connected dual graphs
2011,
It is shown that for every finite set of disjoint convex polygonal obstacles in the...
Why locally‐fair maximal flows in client‐server networks perform well
Why locally‐fair maximal flows in client‐server networks perform well
2011,
Maximal flows reach at least a 1/2 approximation of the maximum flow in...
Strongly chordal and chordal bipartite graphs are sandwich monotone
Strongly chordal and chordal bipartite graphs are sandwich monotone
2011,
A graph class is sandwich monotone if, for every pair of its graphs G 1 =( V , E 1 )...
On the Diaconis‐Gangolli Markov chain for sampling contingency tables with cell‐bounded entries
On the Diaconis‐Gangolli Markov chain for sampling contingency tables with cell‐bounded entries
2011,
The problems of uniformly sampling and approximately counting contingency tables have...
Sublinear‐time algorithms for tournament graphs
Sublinear‐time algorithms for tournament graphs
2011,
We show that a random walk on a tournament on n vertices finds either a sink or a...
Separating NE from some nonuniform nondeterministic complexity classes
Separating NE from some nonuniform nondeterministic complexity classes
2011,
We investigate the question whether NE can be separated from the reduction closures of...
On the readability of monotone Boolean formulae
On the readability of monotone Boolean formulae
2011,
Golumbic et al. (2006) defined the readability of a monotone Boolean function f to be...
Papers per page: