Publications related to Complete bipartite graph

Towards Tight Lower Bounds for Scheduling Problems

We show a close connection between structural hardness for k-partite graphs and tight inapproximability results for scheduling problems with precedence constraints. Assuming a natural but nontrivial generalisation of the bipartite structural hardness resul ...

Springer Int Publishing Ag2015

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Michel Bierlaire, Bilal Farooq, Dimitrios Efthymiou, Paul Richard Anderson

The generation of synthetic populations through simulation methods is an important research topic and has a key application in agent-based modeling of transport and land use. The next step in this research area is the generation of complete synthetic house ...

Natl Acad Sciences2014

Outerplanar graph drawings with few slopes

Bartosz Maria Walczak

We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that Delta - 1 edge slopes suffic ...

Elsevier Science Bv2014

Decomposition and tractability in qualitative spatial and temporal reasoning

Jingshi Li

Constraint networks in qualitative spatial and temporal reasoning (QSTR) typically feature variables defined on infinite domains. Mainstream algorithms for deciding network consistency are based on searching for network refinements whose consistency is kno ...

Elsevier2013

Synthesizing Data on Agents and Their Associations: A Simulation and Graph Theoretic Approach

Michel Bierlaire, Bilal Farooq

Data on the entire population is almost never publicly available. Moreover, there is an alarming trend of discontinuing the exercise of conducting full Census in many countries (Belgium, Switzerland, etc.). In this context, population synthesis techniques ...

2013

Population Synthesis: A Different Perspective

Michel Bierlaire, Bilal Farooq

Microsimulation of urban systems evolution requires synthetic population as a key input. Currently, the focus is on treating synthesis as a fitting problem and thus various techniques have been developed, including Iterative Proportional Fitting (IPF) and ...

2013

On some coloring problems in grids

Dominique de Werra

We study complexity issues related to some coloring problems in grids: we examine in particular the case of List coloring, of Precoloring extension and of (p, q)-List coloring, the case of List coloring in bipartite graphs where lists in the first part of ...

2013

Simplex solids in SU(N) Heisenberg models on the kagome and checkerboard lattices

Frédéric Mila, Karlo Penc

We present a numerical study of the SU(N) Heisenberg model with the fundamental representation at each site for the kagome lattice (for N = 3) and the checkerboard lattice (for N = 4), which are the line graphs of the honeycomb and square lattices and thus ...

2012

Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games

Yannick Rochat

By combining evolutionary game theory and graph theory, “games on graphs” study the evolutionary dynamics of frequency-dependent selection in population structures modeled as geographical or social networks. Networks are usually represented by means of uni ...

Public Library of Science2012

Graph-Constrained Group Testing

Amin Karbasi, Mahdi Cheraghchi Bashi Astaneh, Soheil Mohajerzefreh

Non-adaptive group testing involves grouping arbitrary subsets of

n

items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most

d

d ...

2012

Complete bipartite graph

Graph Chatbot

Chat with Graph Search

Towards Tight Lower Bounds for Scheduling Problems

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Outerplanar graph drawings with few slopes

Decomposition and tractability in qualitative spatial and temporal reasoning

Synthesizing Data on Agents and Their Associations: A Simulation and Graph Theoretic Approach

Population Synthesis: A Different Perspective

On some coloring problems in grids

Simplex solids in SU(N) Heisenberg models on the kagome and checkerboard lattices

Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games

Graph-Constrained Group Testing

Population Synthesis: A Different Perspective

On some coloring problems in grids

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Outerplanar graph drawings with few slopes

Towards Tight Lower Bounds for Scheduling Problems

Synthesizing Data on Agents and Their Associations: A Simulation and Graph Theoretic Approach

Graph-Constrained Group Testing

Decomposition and tractability in qualitative spatial and temporal reasoning

Simplex solids in SU(N) Heisenberg models on the kagome and checkerboard lattices

Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games