A note on exact algorithms for vertex ordering problems on graphs
DOI10.1007/S00224-011-9312-0zbMATH Open1253.68164OpenAlexW2143693959WikidataQ59567532 ScholiaQ59567532MaRDI QIDQ692902FDOQ692902
Hans L. Bodlaender, Arie M. C. A. Koster, Dieter Kratsch, Fedor V. Fomin, Dimitrios M. Thilikos
Publication date: 6 December 2012
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-011-9312-0
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- A Dynamic Programming Approach to Sequencing Problems
- A partial k-arboretum of graphs with bounded treewidth
- On Exact Algorithms for Treewidth
- Some simplified NP-complete graph problems
- The vertex separation number of a graph equals its path-width
- Fugitive-search games on graphs and related parameters
- Finding Induced Subgraphs via Minimal Triangulations
- Exact Algorithms for Treewidth and Minimum Fill-In
- Computing Pathwidth Faster Than 2 n
- Title not available (Why is that?)
- Expected Computation Time for Hamiltonian Path problem
- Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
- Automata, Languages and Programming
- Heuristic and metaheuristic methods for computing graph treewidth
Cited In (25)
- On exact algorithms for the permutation CSP
- Exact algorithms for intervalizing coloured graphs
- On the Equivalence among Problems of Bounded Width
- Vertex ordering with optimal number of adjacent predecessors
- Minimal NMR distance information for rigidity of protein graphs
- On distance-preserving elimination orderings in graphs: complexity and algorithms
- Computing directed pathwidth in \(O(1.89^n)\) time
- Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
- Characterizations and directed path-width of sequence digraphs
- On the approximability of digraph ordering
- Finding small-width connected path decompositions in polynomial time
- Positive-Instance Driven Dynamic Programming for Treewidth.
- On integer linear programs for treewidth based on perfect elimination orderings
- Strong SDP based bounds on the cutwidth of a graph
- An order approach for the core maintenance problem on edge-weighted graphs
- Optimal vertex ordering of graphs
- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- Improved Parameterized Algorithms for above Average Constraint Satisfaction
- Computing the pathwidth of directed graphs with small vertex cover
- Rank-width: algorithmic and structural results
- Ordering transactions with bounded unfairness: definitions, complexity and constructions
- Treewidth and pathwidth parameterized by the vertex cover number
- Computing tree-depth faster than \(2^n\)
- Title not available (Why is that?)
- Title not available (Why is that?)
This page was built for publication: A note on exact algorithms for vertex ordering problems on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692902)
