Concept

Biconnected component

Related publications (35)

On the Page Number of Upward Planar Directed Acyclic Graphs

Radoslav Fulek, Fabrizio Frati, Andres Jacinto Ruiz Vargas

In this paper we study the page number of upward planar directed acyclic graphs. We prove that: (I) the page number of any n-vertex upward planar triangulation G whose every maximal 4-connected component has page number k is at most min {O(k log n), O(2(k) ...

Springer-Verlag Berlin2011

Fast Computation of Small Cuts via Cycle Space Sampling

David Pritchard

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space iden ...

2011

On the connectivity of visibility graphs

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibil ...

2011

Sup-norms of Eigenfunctions on Arithmetic Ellipsoids

Philippe Michel

Let B be a positive quaternion algebra, and let O subset of B be an Eichler order. There is associated, in a natural way, a variety X = X(O) the connected components of which are indexed by the ideal classes of O and are isomorphic to spheres. This variety ...

Oxford University Press2011

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

Information Flow Decomposition for Network Coding

Christina Fragouli, Emina Soljanin

The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding ...

2006

Information flow decomposiiton for network coding

Christina Fragouli, Emina Soljanin

Institute of Electrical and Electronics Engineers2006

Numerical simulation of free surface incompressible liquid flows surrounded by compressible gas

Jacques Rappaz, Marco Picasso, Alexandre Caboussat

A numerical model for the three-dimensional simulation of liquid-gas flows with free surfaces is presented. The incompressible Navier-Stokes equations are assumed to hold in the liquid domain. In the gas domain, the velocity is disregarded, the pressure is ...

2005

A Connection between Network Coding and Convolutional Codes

Christina Fragouli, Emina Soljanin

The min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by liner re-encoding at node ...

2004

Information Flow Decomposition for Network Coding

Christina Fragouli, Emina Soljanin

2004

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.