An Experimental Study of the Treewidth of Real-World Graph Data
From MaRDI portal
Publication:5091123
DOI10.4230/LIPIcs.ICDT.2019.12OpenAlexW2908404314MaRDI QIDQ5091123
Silviu Maniu, Suraj Jog, Pierre Senellart
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1901.06862
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties ⋮ Solving projected model counting by utilizing treewidth and its limits ⋮ Maximizing Social Welfare in Score-Based Social Distance Games ⋮ Unnamed Item ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Knowledge compilation meets database theory: compiling queries to decision diagrams
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
- Treewidth computations. II. Lower bounds
- Graph minors. III. Planar tree-width
- Approximation algorithms for treewidth
- Treewidth computations. I: Upper bounds
- The closure of monadic NP
- SAT-based local improvement for finding tree decompositions of small width
- Descriptive complexity of \(\#\)P functions
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The Elimination form of the Inverse and its Application to Linear Programming
- Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
- Enumeration Complexity of Logical Query Problems with Second-order Variables
- On exact algorithms for treewidth
- Enumeration of monadic second-order queries on trees
- Statistical mechanics of complex networks
- Deciding first-order properties of locally tree-decomposable structures
- Connecting Width and Structure in Knowledge Compilation (Extended Version)
- Provenance Circuits for Trees and Treelike Instances
- Query evaluation via tree-decompositions
- MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
- Complexity of Finding Embeddings in a k-Tree
- Random graph models of social networks
- An Indexing Framework for Queries on Probabilistic Graphs
- When is the evaluation of conjunctive queries tractable?
- Customizable Contraction Hierarchies
- Structure of Graphs with Locally Restricted Crossings
- Collective dynamics of ‘small-world’ networks
- The dichotomy of probabilistic inference for unions of conjunctive queries
- Directed Nowhere Dense Classes of Graphs
- Algorithms – ESA 2004
- Generalized finite automata theory with an application to a decision problem of second-order logic
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Experimental and Efficient Algorithms
- Tree decompositions and social graphs
- Principles and Practice of Constraint Programming – CP 2004
- Graph-Theoretic Concepts in Computer Science
