Publications related to Complete bipartite graph

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Given an undirected graph G = (V, E) with matching number nu(G), a d-blocker is a subset of edges B such that nu((V, E \ B))

2010

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 and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagati ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

Three-Sublattice Ordering of the SU(3) Heisenberg Model of Three-Flavor Fermions on the Square and Cubic Lattices

Frédéric Mila, Karlo Penc, Tamás András Tóth

Combining a semiclassical analysis with exact diagonalizations, we show that the ground state of the SU(3) Heisenberg model on the square lattice develops three-sublattice long-range order. This surprising pattern for a bipartite lattice with only nearest- ...

2010

Degree-constrained edge partitioning in graphs arising from discrete tomography

Dominique de Werra, Bernard Ries

Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...

2009

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Dominique de Werra

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...

2009

Exact Solution of the Gauge Symmetric p-Spin Glass Model on a Complete Graph

Nicolas Macris, Satish Babu Korada

We consider a gauge symmetric version of the p-spin glass model on a complete graph. The gauge symmetry guarantees the absence of replica symmetry breaking and allows to fully use the interpolation scheme of Guerra to rigorously compute the free energy. In ...

2009

A separator theorem for string graphs and its applications

János Pach

A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with in edges can be separated into two parts of roughly equal size by the removal of O(m(3/4)root log m) vertices. This result is then ...

Springer2009

Mixed graph edge coloring

Bernard Ries

We are interested in coloring the edges of a mixed graph. i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds oil the number of requ ...

Elsevier2009

Using Three States for Binary Consensus on Complete Graphs

Etienne Perron, Dinkar Vasudevan, Milan Vojnovic

We consider the binary consensus problem where each node in the network initially observes one of two states and the goal for each node is to eventually decide which one of the two states was initially held by the majority of the nodes. Each node contacts ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009

Distributed average consensus for wireless sensor networks

Florence Bénézit

Wireless sensor networks have emerged a few years ago, enabling large scale sensing at low cost. There are many interesting problems related to this new sensing tool: designing robust and small hardware, defining adapted routing protocols, minimizing the e ...

EPFL2009

Complete bipartite graph

Graph Chatbot

Chat with Graph Search

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Graph-Constrained Group Testing

Three-Sublattice Ordering of the SU(3) Heisenberg Model of Three-Flavor Fermions on the Square and Cubic Lattices

Degree-constrained edge partitioning in graphs arising from discrete tomography

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Exact Solution of the Gauge Symmetric p-Spin Glass Model on a Complete Graph

A separator theorem for string graphs and its applications

Mixed graph edge coloring

Using Three States for Binary Consensus on Complete Graphs

Distributed average consensus for wireless sensor networks

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Graph-Constrained Group Testing

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Three-Sublattice Ordering of the SU(3) Heisenberg Model of Three-Flavor Fermions on the Square and Cubic Lattices

Degree-constrained edge partitioning in graphs arising from discrete tomography

Exact Solution of the Gauge Symmetric p-Spin Glass Model on a Complete Graph

A separator theorem for string graphs and its applications

Mixed graph edge coloring

Using Three States for Binary Consensus on Complete Graphs

Distributed average consensus for wireless sensor networks