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

DOI10.4230/LIPICS.ICALP.2019.109MaRDI QIDQ5091271FDOQ5091271

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

Recommendations

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

zbMATH Keywords

approximation algorithmsNP-completenessgraph and string parameters

Mathematics Subject Classification ID

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

Cites Work

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

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)