scientific article
From MaRDI portal
Publication:3386630
DOI10.23638/DMTCS-22-4-8zbMath1454.68158MaRDI QIDQ3386630
Martin Koutecký, Hans Raj Tiwary, Petr Kolman
Publication date: 5 January 2021
Full work available at URL: https://dmtcs.episciences.org/6811
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Logic in computer science (03B70) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (4)
Principled deep neural network training through linear programming ⋮ The role of rationality in integer-programming relaxations ⋮ On permuting some coordinates of polytopes ⋮ A tight approximation algorithm for the cluster vertex deletion problem
Cites Work
- The projected faces property and polyhedral relations
- Finding paths with minimum shared edges
- Courcelle's theorem -- a game-theoretic approach
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- The minimum vulnerability problem
- Monadic second-order evaluations on tree-decomposable graphs
- Elements of finite model theory.
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- On the extension complexity of combinatorial polytopes
- Extended formulation for CSP that is compact for instances of bounded treewidth
- Expressing combinatorial optimization problems by linear programs
- Treewidth. Computations and approximations
- Conjunctive-query containment and constraint satisfaction
- The complexity of first-order and monadic second-order logic revisited
- Linear time solvable optimization problems on graphs of bounded clique-width
- Practical access to dynamic programming on tree decompositions
- Information-theoretic approximations of the nonnegative rank
- Parameterized extension complexity of independent set and related problems
- A class of games possessing pure-strategy Nash equilibria
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Monadic datalog over finite structures of bounded treewidth
- Constructing Extended Formulations from Reflection Relations
- Easy problems for tree-decomposable graphs
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Polyhedral Characterization of Discrete Dynamic Programming
- Algorithmic Meta-theorems
- Treewidth: Characterizations, Applications, and Computations
- Reformulation and Decomposition of Integer Programs
- Branched Polyhedral Systems
- The Linear Programming Polytope of Binary Constraint Problems with Bounded Tree-Width
- Lectures on Polytopes
- Evaluation of an MSO-Solver
- A linear time algorithm for finding tree-decompositions of small treewidth
- The Polytope of Tree-Structured Binary Constraint Satisfaction Problems
- Finding Branch-Decompositions and Rank-Decompositions
- Extended formulations from communication protocols in output-efficient time
- Extended formulations in combinatorial optimization
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
