Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Pseudoforest

Related publications (22)

Scalable maximal subgraph mining with backbone-preserving graph convolutions

Karl Aberer, Thành Tâm Nguyên, Quoc Viet Hung Nguyen, Thanh Trung Huynh

Maximal subgraph mining is increasingly important in various domains, including bioinformatics, genomics, and chemistry, as it helps identify common characteristics among a set of graphs and enables their classification into different categories. Existing ...

ELSEVIER SCIENCE INC2023

Motif Cut Sparsifiers

Mikhail Kapralov, Jakab Tardos, Mikhail Makarov

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

Thrackles: An improved upper bound

János Pach, Radoslav Fulek

A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, ex ...

ELSEVIER SCIENCE BV2019

Time-resolved analysis of dynamic graphs: an extended Slepian design

Dimitri Nestor Alice Van De Ville, Raphaël Pierre Liégeois

Graphs are extensively used to represent networked data. In many applications, especially when considering large datasets, it is a desirable feature to focus the analysis onto specific subgraphs of interest. Slepian theory and its extension to graphs allow ...

SPIE-INT SOC OPTICAL ENGINEERING2019

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

Ola Nils Anders Svensson

A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs ...

IEEE COMPUTER SOC2019

Monopulse Beam Synthesis Using a Sparse Single Layer of Weights

Semin Kwak

A conventional monopulse radar system uses three beams, namely, sum beam, elevation difference beam, and azimuth difference beam, which require different layers of weights to synthesize each beam independently. Since the multilayer structure increases the ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019

Generating and identifying functional subnetworks within structural networks

Henry Markram, Kathryn Hess Bellwald, Michael Reimann, Max Christian Nolte, Ran Levi

In one aspect, a method includes generating a functional subgraph of a network from a structural graph of the network. The structural graph comprises a set of vertices and structural connections between the vertices. Generating the functional subgraph incl ...

2018

Graph Heat Mixture Model Learning

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic

Graph inference methods have recently attracted a great interest from the scientific community, due to the large value they bring in data interpretation and analysis. However, most of the available state-of-the-art methods focus on scenarios where all avai ...

IEEE2018

When Stuck, Flip a Coin : New Algorithms for Large-Scale Tasks

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Justin Dean Ward

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or ...

INFORMS2017

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Tangles and Degenerate Tangles

Andres Jacinto Ruiz Vargas

We study some variants of Conway’s thrackle conjecture. A tangle is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at wh ...

Springer Berlin Heidelberg2013

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

A computational approach to Conway's thrackle conjecture

János Pach, Radoslav Fulek

A drawing of a graph in the plane is called a thrackle if every pair of edges meets precisely once, either at a common vertex or at a proper crossing. Let t(n) denote the maximum number of edges that a thrackle of n vertices can have. According to a 40 yea ...

2011

A Computational Approach to Conway's Thrackle Conjecture

János Pach, Radoslav Fulek

Springer2010

QoSNC: A Novel Approach to QoS-Based Network Coding for Fixed Networks

Amir Hesam Salavati

In this paper, we present a decentralized algorithm to find minimum cost quality of service (QoS) flow subgraphs in network coded multicast schemes. The main objective is to find minimum cost subgraphs that also satisfy user-specified QoS constraints, spec ...

2010

The Holt-Klee condition for oriented matroids

Holt and Klee have recently shown that every (generic) LP orientation of the graph of a d-polytope satisfies a directed version of the d-connectivity property, i.e. there are d internally disjoint directed paths from a unique source to a unique sink. We in ...

2009

Feedback topology and XOR-dynamics in Boolean networks with varying input structure

Carlo Maffi

We analyze a model of fixed in-degree random Boolean networks in which the fraction of input-receiving nodes is controlled by the parameter gamma. We investigate analytically and numerically the dynamics of graphs under a parallel XOR updating scheme. This ...

2009

Coloring Fuzzy Circular Interval Graphs

Friedrich Eisenbrand, Martin Niemeier

Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs ...

Elsevier2009

Related publications (22)

3

. Then, we draw a connection to Goem ...

EPFL2014