Planar orientations with low out-degree and compaction of adjacency matrices
From MaRDI portal
Publication:1178710
DOI10.1016/0304-3975(91)90020-3zbMath0735.68015OpenAlexW2022783258WikidataQ57259019 ScholiaQ57259019MaRDI QIDQ1178710
Publication date: 26 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(91)90020-3
Related Items
Arboricity and bipartite subgraph listing algorithms, On the (near) optimality of extended formulations for multi-way cut in social networks, Straight-Line Drawability of a Planar Graph Plus an Edge, Simultaneously load balancing for every p-norm, with reassignments, Adjacency queries in dynamic sparse graphs, On the Most Imbalanced Orientation of a Graph, On a vertex-edge marking game on graphs, Parameterized orientable deletion, On low tree-depth decompositions, Grad and classes with bounded expansion. II: Algorithmic aspects, Minimize the maximum duty in multi-interface networks, A connection between sports and matroids: how many teams can we beat?, Bounded outdegree and extremal length on discrete Riemann surfaces, Asymmetric marking games on line graphs, Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree, Balanced vertex-orderings of graphs, On the most imbalanced orientation of a graph, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, Graph orientation with splits, Degree-constrained orientations of embedded graphs, Min-Max Coverage in Multi-interface Networks, Two-dimensional viscous flow computations on the Connection Machine: Unstructured meshes, upwind schemes and massively parallel computations, Unnamed Item, Upper and lower degree-constrained graph orientation with minimum penalty, Why Do Simple Algorithms for Triangle Enumeration Work in the Real World?, Combinatorial modulus and type of graphs, Navigating planar topologies in near-optimal space and time, Graph Orientation with Edge Modifications, GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE, Degree-constrained graph orientation: maximum satisfaction and minimum violation, Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs
Cites Work
- An efficient parallel algorithm for computing a large independent set in a planar graph
- Parallel recognition and decomposition of two terminal series parallel graphs
- Parallel recognition of series-parallel graphs
- Parallel concepts in graph theory
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- Edge-Disjoint Spanning Trees of Finite Graphs
- Arboricity and Subgraph Listing Algorithms
- An Efficient Parallel Biconnectivity Algorithm
- Parallel Prefix Computation
- An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
- Efficient Planarity Testing
- Finding a Minimum Circuit in a Graph
- Optimal Parallel 5-Colouring of Planar Graphs
- The Parallel Evaluation of General Arithmetic Expressions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
