Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
From MaRDI portal
Publication:724225
DOI10.1007/s00453-017-0399-9zbMath1393.68067OpenAlexW2773733755WikidataQ59567349 ScholiaQ59567349MaRDI QIDQ724225
Hirotaka Ono, Hans L. Bodlaender, Yota Otachi
Publication date: 25 July 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6789/
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07)
Related Items
Parameterized orientable deletion, Unnamed Item, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
Cites Work
- Unnamed Item
- Degree-constrained graph orientation: maximum satisfaction and minimum violation
- Recognizability equals definability for graphs of bounded treewidth and bounded chordality
- On finding orientations with the fewest number of vertices with small out-degree
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- The parameterized complexity of editing graphs for bounded degeneracy
- Planar orientations with low out-degree and compaction of adjacency matrices
- Treewidth of cocomparability graphs and a new order-theoretic parameter
- Listing all potential maximal cliques of a graph
- The monadic second-order logic of graphs. VIII: Orientations
- Parameterized complexity of finding subgraphs with hereditary properties.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Minimizing maximum indegree
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Approximating clique-width and branch-width
- On the degrees of the vertices of a directed graph
- Acyclic orientations of graphs
- Exponential time algorithms for the minimum dominating set problem on some graph classes
- Large Induced Subgraphs via Triangulations and CMSO
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- Representation of a finite graph by a set of intervals on the real line
- Easy problems for tree-decomposable graphs
- GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
- Clique-Width is NP-Complete
- Upper degree-constrained partial orientations
- Smallest-last ordering and clustering and graph coloring algorithms
- Strongly connected orientations of mixed multigraphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Minimum Fill-in on Circle and Circular-Arc Graphs
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- Treewidth of Chordal Bipartite Graphs
- Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n
- On the Relationship Between Clique-Width and Treewidth
- Definability Equals Recognizability for $k$-Outerplanar Graphs
- Parameterized Algorithms
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Graph Orientations Optimizing the Number of Light or Heavy Vertices
- Graph-Theoretic Concepts in Computer Science
