scientific article; zbMATH DE number 7561602

DOI10.4230/LIPICS.ICALP.2019.109MaRDI QIDQ5091271

Joel D. Day, Markus L. Schmid, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea, Katrin Casel

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1902.10983

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

NP-completenessapproximation algorithmsgraph and string parameters

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (2)

Blocksequences of \(k\)-local words ⋮ Strong SDP based bounds on the cutwidth of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parameterised complexity of string morphism problems
• Extended regular expressions: succinctness and decidability
• Fundamentals of parameterized complexity
• Patterns with bounded treewidth
• A note on exact algorithms for vertex ordering problems on graphs
• Developments from enquiries into the learnability of the pattern languages from positive data
• Discontinuities in pattern inference
• Finding patterns common to a set of strings
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• On matching generalised repetitive patterns
• Deterministic regular expressions with back-references
• Pattern matching with variables: a multivariate complexity analysis
• Generalized function matching
• Parametrized complexity theory.
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Revisiting Shinohara's algorithm for computing descriptive patterns
• Graph expansion and the unique games conjecture
• Fixed-Parameter Tractability of Treewidth and Pathwidth
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Subexponential Algorithms for Unique Games and Related Problems
• On the power of unique 2-prover 1-round games
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Computing Pathwidth Faster Than 2 n
• Topological Bandwidth
• The expressibility of languages and relations by word equations
• Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
• Inapproximability of Treewidth and Related Problems
• Cutwidth I: A linear time fixed parameter algorithm
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Expander flows, geometric embeddings and graph partitioning
• Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries

This page was built for publication: