Weighted proper orientations of trees and graphs of bounded treewidth

DOI10.1016/j.tcs.2018.11.013zbMath1421.68104arXiv1804.03884OpenAlexW2962762415MaRDI QIDQ2632010

Yanyan Li

Publication date: 17 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

treewidthtreesparameterized complexityproper orientation number\(\mathsf{W} [1\)-hardness]minimum maximum indegreeweighted proper orientation number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

On the proper orientation number of chordal graphs ⋮ Note on (semi-)proper orientation of some triangulated planar graphs ⋮ On the semi-proper orientations of graphs ⋮ Proper orientation, proper biorientation and semi-proper orientation numbers of graphs ⋮ On the in-out-proper orientations of graphs ⋮ On the proper arc labeling of directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Proper orientation of cacti
• Fundamentals of parameterized complexity
• On the proper orientation number of bipartite graphs
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Graph minors. III. Planar tree-width
• Treewidth. Computations and approximations
• On variations of the subset sum problem
• Which problems have strongly exponential complexity?
• Proper orientations of planar bipartite graphs
• The complexity of the proper orientation number
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Monadic second order logic on graphs with local cardinality constraints
• Reducibility among Combinatorial Problems
• Weighted Coloring in Trees
• Parameterized Algorithms
• Ruling out FPT algorithms for weighted coloring on forests

This page was built for publication: Weighted proper orientations of trees and graphs of bounded treewidth