On the public citation graph
Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
0 signed · 138 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/bf02280884openalex-snapshot
The NP-Completeness of the bandwidth minimization problem
inferredcites →https://doi.org/10.1016/0304-3975(76)90059-1openalex-snapshot
Some simplified NP-complete graph problems
inferredcites →https://doi.org/10.1137/0134037openalex-snapshot
Complexity Results for Bandwidth Minimization
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.2139/ssrn.4673490openalex-extracted
Parameterized Problems Complete for Nondeterministic Fpt Time and Logarithmic Space
inferred← citeshttps://doi.org/10.1002/jgt.10496openalex-snapshot
Self‐clique graphs and matrix permutations
inferred← citeshttps://doi.org/10.1002/jgt.3190060302openalex-snapshot
The bandwidth problem for graphs and matrices—a survey
inferred← citeshttps://doi.org/10.1006/inco.1994.1064openalex-snapshot
The Vertex Separation and Search Number of a Graph
inferred← citeshttps://doi.org/10.1006/jcss.1999.1682openalex-snapshot
Approximating the Bandwidth via Volume Respecting Embeddings
inferred← citeshttps://doi.org/10.1007/11538462_6openalex-snapshot
Approximating the Bandwidth of Caterpillars
inferred← citeshttps://doi.org/10.1007/3-540-10291-4_12openalex-snapshot
Issues in the study of graph embeddings
inferred← citeshttps://doi.org/10.1007/3-540-10291-4_20openalex-snapshot
Bounding the bandwidth of NP-complete problems
inferred← citeshttps://doi.org/10.1007/3-540-10291-4_21openalex-snapshot
The complexity of path problems in graphs and path systems of bounded bandwidth
inferred← citeshttps://doi.org/10.1007/3-540-10856-4_75openalex-snapshot
Time and space bounded complexity classes and bandwidth constrained problems
inferred← citeshttps://doi.org/10.1007/3-540-44985-x_2openalex-snapshot
Coping with the NP-Hardness of the Graph Bandwidth Problem
inferred← citeshttps://doi.org/10.1007/3-540-50728-0_57openalex-snapshot
Bandwidth and profile minimization
inferred← citeshttps://doi.org/10.1007/3-540-54029-6_155openalex-snapshot
Approximation algorithms for the Bandwidth Minimization Problem for a large class of trees
inferred← citeshttps://doi.org/10.1007/3-540-55488-2_21openalex-snapshot
Processing of hierarchically defined graphs and graph families
inferred← citeshttps://doi.org/10.1007/3-540-60084-1_65openalex-snapshot
Intervalizing k-colored graphs
inferred← citeshttps://doi.org/10.1007/978-1-4757-2807-1_1openalex-snapshot
Constraint Satisfaction Methods for Generating Valid Cuts
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_513openalex-snapshot
Exact Algorithms for Bandwidth
inferred← citeshttps://doi.org/10.1007/978-3-030-86838-3_2openalex-snapshot
Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation
inferred← citeshttps://doi.org/10.1007/978-3-030-96731-4_2openalex-snapshot
From the W-hierarchy to XNLP
inferred← citeshttps://doi.org/10.1007/978-3-032-17801-5_21openalex-snapshot
Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
inferred← citeshttps://doi.org/10.1007/978-3-032-27732-9_11openalex-snapshot
The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
inferred← citeshttps://doi.org/10.1007/978-3-319-42849-9openalex-snapshot
Decision Diagrams for Optimization
inferred← citeshttps://doi.org/10.1007/978-3-540-30113-4_12openalex-snapshot
On the Phase Coupling Problem Between Data Memory Layout Generation and Address Pointer Assignment
inferred← citeshttps://doi.org/10.1007/978-3-540-79450-9_13openalex-snapshot
Generalized Gene Adjacencies, Graph Bandwidth and Clusters in Yeast Evolution
inferred← citeshttps://doi.org/10.1007/978-3-642-02927-1_26openalex-snapshot
Exact and Approximate Bandwidth
inferred← citeshttps://doi.org/10.1007/978-3-642-02927-1_39openalex-snapshot
Distortion Is Fixed Parameter Tractable
inferred← citeshttps://doi.org/10.1007/978-3-642-02927-1_8openalex-snapshot
Counting Subgraphs via Homomorphisms
inferred← citeshttps://doi.org/10.1007/978-3-642-10631-6_59openalex-snapshot
Bandwidth on AT-Free Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-11269-0_14openalex-snapshot
An Exponential Time 2-Approximation Algorithm for Bandwidth
inferred← citeshttps://doi.org/10.1007/978-3-642-16181-0_23openalex-snapshot
The Complexity of the Gapped Consecutive-Ones Property Problem for Matrices of Bounded Maximum Degree
inferred← citeshttps://doi.org/10.1007/978-3-642-20036-6_40openalex-snapshot
Opera: Reconstructing Optimal Genomic Scaffolds with High-Throughput Paired-End Sequences
inferred← citeshttps://doi.org/10.1007/978-3-642-21311-3_5openalex-snapshot
Manipulating MDD Relaxations for Combinatorial Optimization
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_513-1openalex-snapshot
Exact Algorithms for Bandwidth
inferred← citeshttps://doi.org/10.1007/978-3-662-43948-7_34openalex-snapshot
Parameterized Complexity of Bandwidth on Trees
inferred← citeshttps://doi.org/10.1007/bf00289115openalex-snapshot
Graph theoretic closure properties of the family of boundary NLC graph languages
inferred← citeshttps://doi.org/10.1007/bf01928924openalex-snapshot
Linear arrangement problems on recursively partitioned graphs
inferred← citeshttps://doi.org/10.1007/bf02090396openalex-snapshot
Bandwidth Minimization: An approximation algorithm for caterpillars
inferred← citeshttps://doi.org/10.1007/bf02579299openalex-snapshot
Bounds on the convex label number of trees
inferred← citeshttps://doi.org/10.1007/bf02679454openalex-snapshot
Approximation algorithms for the bandwidth minimization problem for a large class of trees
inferred← citeshttps://doi.org/10.1007/bfb0029946openalex-snapshot
Treewidth: Algorithmic techniques and results
inferred← citeshttps://doi.org/10.1007/bfb0036931openalex-snapshot
Minimizing width in linear layouts
inferred← citeshttps://doi.org/10.1007/pl00009277openalex-snapshot
Bounded Degree Interval Sandwich Problems
inferred← citeshttps://doi.org/10.1007/s00224-020-09967-8openalex-snapshot
Token Sliding on Split Graphs
inferred← citeshttps://doi.org/10.1007/s00224-024-10202-xopenalex-snapshot
Exact and Approximate Digraph Bandwidth
inferred← citeshttps://doi.org/10.1007/s00453-007-9002-0openalex-snapshot
Approximating the Bandwidth of Caterpillars
inferred← citeshttps://doi.org/10.1007/s00453-025-01315-xopenalex-snapshot
Bandwidth Parameterized by Cluster Vertex Deletion Number
inferred← citeshttps://doi.org/10.1007/s10601-015-9217-7openalex-snapshot
New techniques for discrete optimization
inferred← citeshttps://doi.org/10.1007/s10732-014-9238-1openalex-snapshot
BDD-based heuristics for binary optimization
inferred← citeshttps://doi.org/10.1016/0020-0190(87)90173-6openalex-snapshot
The complexity of minimizing wire lengths in VLSI layouts
inferred← citeshttps://doi.org/10.1016/0020-0190(89)90140-3openalex-snapshot
Undecidability of the bandwidth problem on linear graph languages
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90108-8openalex-snapshot
On the complexity of tree embedding problems
inferred← citeshttps://doi.org/10.1016/0095-8956(87)90052-9openalex-snapshot
Bandwidths and profiles of trees
inferred← citeshttps://doi.org/10.1016/0166-218x(92)90229-4openalex-snapshot
Optimal linear labelings and eigenvalues of graphs
inferred← citeshttps://doi.org/10.1016/0196-6774(82)90011-6openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0196-6774(82)90026-8openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0196-6774(84)90006-3openalex-snapshot
Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
inferred← citeshttps://doi.org/10.1016/0196-6774(85)90012-4openalex-snapshot
The NP-completeness column: an ongoing guide
inferred← citeshttps://doi.org/10.1016/0196-6774(85)90016-1openalex-snapshot
NP-completeness for minimizing maximum edge length in grid embeddings
inferred← citeshttps://doi.org/10.1016/0196-6774(86)90020-9openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0196-6774(87)90039-3openalex-snapshot
Linear-time computation of optimal subgraphs of decomposable graphs
inferred← citeshttps://doi.org/10.1016/0304-3975(85)90068-4openalex-snapshot
Bandwidth constrained NP-complete problems
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00185-9openalex-snapshot
Two-Dimensional partitioning problems
inferred← citeshttps://doi.org/10.1016/0890-5401(87)90028-9openalex-snapshot
Finding the minimum bandwidth of an interval graph
inferred← citeshttps://doi.org/10.1016/0890-5401(90)90027-fopenalex-snapshot
The complexity of finding uniform emulations on paths and ring networks
inferred← citeshttps://doi.org/10.1016/j.apal.2003.11.002openalex-snapshot
Algorithmic uses of the Feferman–Vaught Theorem
inferred← citeshttps://doi.org/10.1016/j.dam.2012.03.019openalex-snapshot
Hardness results on the gapped consecutive-ones property problem
inferred← citeshttps://doi.org/10.1016/j.endm.2009.07.020openalex-snapshot
On the Gapped Consecutive-Ones Property
inferred← citeshttps://doi.org/10.1016/j.ic.2024.105195openalex-snapshot
Parameterized problems complete for nondeterministic FPT time and logarithmic space
inferred← citeshttps://doi.org/10.1016/j.jcss.2010.06.006openalex-snapshot
Hardness results for approximating the bandwidth
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.06.018openalex-snapshot
Exact and approximate bandwidth
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.09.011openalex-snapshot
Bandwidth on AT-free graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.03.024openalex-snapshot
An exponential time 2-approximation algorithm for bandwidth
inferred← citeshttps://doi.org/10.1016/s0167-5060(08)70455-2openalex-snapshot
Bandwidth versus Bandsize
inferred← citeshttps://doi.org/10.1016/s0304-3975(03)00238-xopenalex-snapshot
The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
inferred← citeshttps://doi.org/10.1023/a:1008961206784openalex-snapshot
Minimization of Data Address Computation Overhead in DSP Programs
inferred← citeshttps://doi.org/10.1080/10556788.2012.709856openalex-snapshot
On semidefinite programming bounds for graph bandwidth
inferred← citeshttps://doi.org/10.1089/cmb.2011.0128openalex-snapshot
The Complexity of the Gapped Consecutive-Ones Property Problem for Matrices of Bounded Maximum Degree
inferred← citeshttps://doi.org/10.1089/cmb.2011.0170openalex-snapshot
Opera: Reconstructing Optimal Genomic Scaffolds with High-Throughput Paired-End Sequences
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00027openalex-snapshot
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
inferred← citeshttps://doi.org/10.1109/icassp.1997.599860openalex-snapshot
Constructing memory layouts for address generation units supporting offset 2 access
inferred← citeshttps://doi.org/10.1109/icassp.1998.678180openalex-snapshot
Minimization of data address computation overhead in DSP programs
inferred← citeshttps://doi.org/10.1109/icdcs.2013.45openalex-snapshot
On the k-Atomicity-Verification Problem
inferred← citeshttps://doi.org/10.1109/infcomw.2016.7562077openalex-snapshot
Computing road signatures from cell sequences with minimum inconsistencies
inferred← citeshttps://doi.org/10.1109/sfcs.1980.17openalex-snapshot
Efficient algorithms for path system problems and applications to alternating and time-space complexity classes
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365715openalex-snapshot
Tractability of parameterized completion problems on chordal and interval graphs: minimum fill-in and physical mapping
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743431openalex-snapshot
The complexity of the approximation of the bandwidth problem
inferred← citeshttps://doi.org/10.1109/spdp.1990.143552openalex-snapshot
Approximation algorithms for the bandwidth minimization problem for caterpillar graphs
inferred← citeshttps://doi.org/10.1109/tcbb.2008.121openalex-snapshot
Generalized Gene Adjacencies, Graph Bandwidth, and Clusters in Yeast Evolution
inferred← citeshttps://doi.org/10.1134/s1990478917010112openalex-snapshot
Critical elements in combinatorially closed families of graph classes
inferred← citeshttps://doi.org/10.1137/0217064openalex-snapshot
A Linear Algorithm for Topological Bandwidth in Degree-Three Trees
inferred← citeshttps://doi.org/10.1137/0607057openalex-snapshot
The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
inferred← citeshttps://doi.org/10.1137/080712921openalex-snapshot
Low Distortion Maps Between Point Sets
inferred← citeshttps://doi.org/10.1137/100789403openalex-snapshot
Counting Subgraphs via Homomorphisms
inferred← citeshttps://doi.org/10.1137/16m1056389openalex-snapshot
Computing $k$-Atomicity in Polynomial Time
inferred← citeshttps://doi.org/10.1137/17m1113527openalex-snapshot
Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces
inferred← citeshttps://doi.org/10.1137/s0097539793258143openalex-snapshot
Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
inferred← citeshttps://doi.org/10.1137/s0895480199351148openalex-snapshot
Testing Bandwidth k for k -Connected Graphs
inferred← citeshttps://doi.org/10.1145/1007352.1007398openalex-snapshot
Low distortion maps between point sets
inferred← citeshttps://doi.org/10.1145/1374376.1374384openalex-snapshot
Algorithms for subset selection in linear regression
inferred← citeshttps://doi.org/10.1145/168304.168314openalex-snapshot
Learning and robust learning of product distributions
inferred← citeshttps://doi.org/10.1145/195058.195229openalex-snapshot
Beyond NP-completeness for problems of bounded width (extended abstract)
inferred← citeshttps://doi.org/10.1145/1993806.1993834openalex-snapshot
Analyzing consistency properties for fun and profit
inferred← citeshttps://doi.org/10.1145/2489789openalex-snapshot
Distortion is Fixed Parameter Tractable
inferred← citeshttps://doi.org/10.1145/276698.276716openalex-snapshot
Approximating the bandwidth via volume respecting embeddings (extended abstract)
inferred← citeshttps://doi.org/10.1145/2767386.2767407openalex-snapshot
Computing Weak Consistency in Polynomial Time
inferred← citeshttps://doi.org/10.1145/3458744.3473365openalex-snapshot
Towards Faster Execution of Ensemble ML Bootstrap Based Techniques
inferred← citeshttps://doi.org/10.1145/3798129.3800723openalex-snapshot
Forbidden Subgraphs of Graphs with Low Bandwidth
inferred← citeshttps://doi.org/10.1145/568522.568523openalex-snapshot
A survey of graph layout problems
inferred← citeshttps://doi.org/10.1145/800061.808778openalex-snapshot
Probabilistic analysis of bandwidth minimization algorithms
inferred← citeshttps://doi.org/10.1287/ijoc.14.4.295.2828openalex-snapshot
Logic, Optimization, and Constraint Programming
inferred← citeshttps://doi.org/10.14288/1.0052159openalex-snapshot
Variants of the Consecutive-Ones Property motivated by the reconstruction of ancestral species
inferred← citeshttps://doi.org/10.17760/d20467217openalex-snapshot
Algorithms for network resource allocation under adversarial dynamics and assignment constraints
inferred← citeshttps://doi.org/10.21105/joss.09136openalex-snapshot
MatrixBandwidth.jl: Fast algorithms for matrix bandwidth minimization and recognition
inferred← citeshttps://doi.org/10.21203/rs.3.rs-2602381/v1openalex-snapshot
Exact and Approximate Digraph Bandwidth
inferred← citeshttps://doi.org/10.22331/q-2023-10-18-1145openalex-snapshot
Discovering optimal fermion-qubit mappings through algorithmic enumeration
inferred← citeshttps://doi.org/10.2478/awutm-2014-0019openalex-snapshot
The Bandwidths of a Matrix. A Survey of Algorithms
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2019.70openalex-snapshot
Retracting Graphs to Cycles
inferred← citeshttps://doi.org/10.4230/lipics.isaac.2021.42openalex-snapshot
On the Extended TSP Problem
inferred← citeshttps://doi.org/10.48550/arxiv.0804.3028openalex-snapshot
Parameterized Low-distortion Embeddings - Graph metrics into lines and trees
inferred← citeshttps://doi.org/10.48550/arxiv.0912.0309openalex-snapshot
Hardness Results for the Gapped Consecutive-Ones Property
inferred← citeshttps://doi.org/10.48550/arxiv.1404.7810openalex-snapshot
Parameterized Complexity of Bandwidth on Trees
inferred← citeshttps://doi.org/10.5555/1109557.1109558openalex-snapshot
Confronting hardness using a hybrid approach
inferred← citeshttps://doi.org/10.5935/978-85-7042-079-4openalex-snapshot
Gestão da Produção em Foco - Volume 37
inferred← citeshttps://doi.org/10.70675/2a7d2deaz145ez4ee9z91d4z066559920227openalex-snapshot
Twin-width : lower bounds and approximation algorithms
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.