Exact and approximate digraph bandwidth

DOI10.1007/S00224-024-10202-XMaRDI QIDQ7021359zbMATH OpenFDO

Authors Pallavi Jain, Lawqueen Kanesh, Saket Saurabh, Roohani Sharma

Publication date 28 February 2025

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-024-10202-X

zbMATH Keywords

approximation schemedirected bandwidthexact exponential algorithms

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• An exponential time 2-approximation algorithm for bandwidth
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Bandwidth and distortion revisited
• Bandwidth of bipartite permutation graphs in polynomial time
• Bandwidth on AT-free graphs
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Complexity Results for Bandwidth Minimization
• Computing the Bandwidth of Interval Graphs
• Confronting hardness using a hybrid approach
• Counting \(H-\)colorings of partial \(k-\)trees
• Counting subgraphs via homomorphisms
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Even faster exact bandwidth
• Exact and approximate bandwidth
• Faster Exact Bandwidth
• scientific article; zbMATH DE number 1617243 (Why is no real title available?)
• scientific article; zbMATH DE number 1186230 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Measured descent: A new embedding method for finite metrics
• Parameterized complexity of bandwidth on trees
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• The complexity of the approximation of the bandwidth problem
• The NP-completeness of the bandwidth minimization problem
• Tournament immersion and cutwidth

This page was built for publication: Exact and approximate digraph bandwidth

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