Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
type: Item
instance of: scholarly article
title: Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
zbMATH Open document ID: 1393.68067
author: Hans L. Bodlaender
author: Hirotaka Ono
author: Yota Otachi
published in: Algorithmica
publication date: 2018-07-25T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6789/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6910200
zbMATH Keywords: orientation
zbMATH Keywords: graph class
zbMATH Keywords: width parameter
zbMATH Keywords: parameterized complexity
MaRDI profile type: Publication
OpenAlex ID: W2773733755
Wikidata QID: Q59567349
cites work: Easy problems for tree-decomposable graphs
cites work: Minimizing maximum indegree
cites work: Graph Orientations Optimizing the Number of Light or Heavy Vertices
cites work: Degree-constrained graph orientation: maximum satisfaction and minimum violation
cites work: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
cites work: GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
cites work: Recognizability equals definability for graphs of bounded treewidth and bounded chordality
cites work: Treewidth and Minimum Fill-in on d-Trapezoid Graphs
cites work: Listing all potential maximal cliques of a graph
cites work: Planar orientations with low out-degree and compaction of adjacency matrices
cites work: Strongly connected orientations of mixed multigraphs
cites work: On the Relationship Between Clique-Width and Treewidth
cites work: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
cites work: The monadic second-order logic of graphs. VIII: Orientations
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Upper bounds to the clique width of graphs
cites work: Parameterized Algorithms
cites work: Clique-Width is NP-Complete
cites work: Large Induced Subgraphs via Triangulations and CMSO
cites work: Acyclic orientations of graphs
cites work: Upper degree-constrained partial orientations
cites work: Exponential time algorithms for the minimum dominating set problem on some graph classes
cites work: Q2766682
cites work: Treewidth of cocomparability graphs and a new order-theoretic parameter
cites work: On the degrees of the vertices of a directed graph
cites work: Definability Equals Recognizability for $k$-Outerplanar Graphs
cites work: On finding orientations with the fewest number of vertices with small out-degree
cites work: Parameterized complexity of finding subgraphs with hereditary properties.
cites work: Treewidth of Chordal Bipartite Graphs
cites work: Minimum Fill-in on Circle and Circular-Arc Graphs
cites work: \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: The parameterized complexity of editing graphs for bounded degeneracy
cites work: Smallest-last ordering and clustering and graph coloring algorithms
cites work: On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Approximating clique-width and branch-width
cites work: Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n
cites work: A Theorem on Graphs, with an Application to a Problem of Traffic Control
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
DBLP publication ID: journals/algorithmica/BodlaenderOO18
DOI: 10.1007/S00453-017-0399-9
description: scientific article; zbMATH DE number 6910200