Graph and string parameters: connections between pathwidth, cutwidth and the locality number

DOI10.4230/LIPICS.ICALP.2019.109MaRDI QIDQ5091271zbMATH OpenFDO

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

Publication date 21 July 2022

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

zbMATH Keywords

approximation algorithmsNP-completenessgraph and string parameters

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1854105
• Derivation of algorithms for cutwidth and related graph layout parameters
• Parametrized complexity of length-bounded cuts and multi-cuts

Cites work

• scientific article; zbMATH DE number 67610 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 6131601 (Why is no real title available?)
• scientific article; zbMATH DE number 7278096 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A note on exact algorithms for vertex ordering problems on graphs
• A partial k-arboretum of graphs with bounded treewidth
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Computing Pathwidth Faster Than 2 n
• Cutwidth I: A linear time fixed parameter algorithm
• Deterministic regular expressions with back-references
• Developments from enquiries into the learnability of the pattern languages from positive data
• Discontinuities in pattern inference
• Expander flows, geometric embeddings and graph partitioning
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
• Extended regular expressions: succinctness and decidability
• Finding patterns common to a set of strings
• Fixed-parameter tractability of treewidth and pathwidth
• Fundamentals of parameterized complexity
• Generalized function matching
• Graph expansion and the unique games conjecture
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Inapproximability of treewidth and related problems
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On matching generalised repetitive patterns
• On the parameterised complexity of string morphism problems
• On the power of unique 2-prover 1-round games
• Parametrized complexity theory.
• Pattern matching with variables: a multivariate complexity analysis
• Pattern matching with variables: fast algorithms and new hardness results
• Patterns with bounded treewidth
• Revisiting Shinohara's algorithm for computing descriptive patterns
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Subexponential algorithms for unique games and related problems
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• The expressibility of languages and relations by word equations
• Topological Bandwidth
• Treewidth. Computations and approximations

Cited in

(3)

• Blocksequences of \(k\)-local words
• Strong SDP based bounds on the cutwidth of a graph
• Word-representable graphs from a word's perspective

This page was built for publication: Graph and string parameters: connections between pathwidth, cutwidth and the locality number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091271)