Concept

Pathwidth

Related publications (16)

Scalable maximal subgraph mining with backbone-preserving graph convolutions

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

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

D-Cliques: Compensating for Data Heterogeneity with Topology in Decentralized Federated Learning

Anne-Marie Kermarrec, Erick Lavoie

The convergence speed of machine learning models trained with Federated Learning is significantly affected by non-independent and identically distributed (non-IID) data partitions, even more so in a fully decentralized setting without a central server. In ...

2022

Specular Manifold Sampling for Rendering High-Frequency Caustics and Glints

Wenzel Alban Jakob, Tizian Lucien Zeltner

Scattering from specular surfaces produces complex optical effects that are frequently encountered in realistic scenes: intricate caustics due to focused reflection, multiple refraction, and high-frequency glints from specular microstructure. Yet, despite ...

ASSOC COMPUTING MACHINERY2020

Untangling emergent cortical dynamics: neurons from networks, noise from chaos

Max Christian Nolte

The way in which cortical microcircuit components -- most importantly neurons -- and their connectivity -- the network -- shape and constrain emergent dynamics is a long-standing question in neuroscience. Experimentally observed dynamical properties can of ...

EPFL2019

Signal-Adapted Tight Frames on Graphs

Dimitri Nestor Alice Van De Ville, Hamid Behjat

The analysis of signals on complex topologies modeled by graphs is a topic of increasing importance. Decompositions play a crucial role in the representation and processing of such information. Here, we propose a new tight frame design that is adapted to a ...

Institute of Electrical and Electronics Engineers2016

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

Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion

Yu Lin, Mingfu Shao

Computing the edit distance between two genomes under certain operations is a basic problem in the study of genome evolution. The double-cut-and-join (DCJ) model has formed the basis for most algorithmic research on rearrangements over the last few years. ...

Biomed Central Ltd2012

Admittance Matrix of a Trapezoidal Piezoelectric Heterogeneous Bimorph

Paul Muralt

Bimorph structures are a standard method for transforming the high force of piezoelectric materials into a large deflection. In micro electromechanical systems (MEMS) applications, it is preferable to use structures consisting of a passive substrate (usual ...

Ieee-Inst Electrical Electronics Engineers Inc2012

Coloring fuzzy circular interval graphs

Friedrich Eisenbrand, Martin Niemeier

Given a graph G with nonnegative node labels w, a multiset of stable sets S_1,...,S_k\subseteq V(G) such that each vertex v \in V(G) is contained in w(v) many of these stable sets is called a weighted coloring. The weighted coloring number \chi_w(G) is the ...

Elsevier2012

Pricing on Paths: A PTAS for the Highway Problem

Thomas Rothvoss

In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the assoc ...

2011

Characterizing Path Graphs by Forbidden Induced Subgraphs

A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are mini ...

2009

A Fast and Exact Algorithm for the Median-of-Three Problem: A Graph Decomposition Approach

Wei Xu

In a previous article, we have shown that adequate subgraphs can be used to decompose multiple breakpoint graphs, achieving a dramatic speedup in solving the median problem. In this article, focusing on the median of three problem, we prove more important ...

Mary Ann Liebert2009

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

Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

Zoltán Miklós

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However, i ...

2009

Tree-Based Pursuit: Algorithm and Properties

Pascal Frossard, Pierre Vandergheynst, Philippe Jost

This paper proposes a tree-based pursuit algorithm that efficiently trades off complexity and approximation performance for overcomplete signal expansions. Finding the sparsest representation of a signal using a redundant dictionary is, in general, a NP-Ha ...

2006

On the stable set polytope of claw-free graphs

Gautier Stauffer

In this thesis we focus our attention on the stable set polytope of claw-free graphs. This problem has been open for many years and albeit all the efforts engaged during those last three years, it is still open. This does not mean that no progress has been ...

EPFL2005