NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs (Q4994988): Difference between revisions

Latest revision as of 10:09, 30 July 2024

scientific article; zbMATH DE number 7362094

Language	Label	Description	Also known as
English	NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs	scientific article; zbMATH DE number 7362094

Statements

instance of

scholarly article

0 references

title

NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs (English)

0 references

0 references

0 references

SIAM Journal on Computing

0 references

publication date

22 June 2021

0 references

full work available at URL

https://arxiv.org/abs/1802.00084

0 references

zbMATH Keywords

parallel algorithms

0 references

perfect matching

0 references

graph minors

0 references

mimicking networks

0 references

maximum flow

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Planar Graph Perfect Matching Is in NC

0 references

An approach to the subgraph homeomorphism problem

0 references

All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

0 references

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

0 references

Flows in One-Crossing-Minor-Free Graphs

0 references

Computing mimicking networks

0 references

Fast Parallel Matrix Inversion Algorithms

0 references

Planar Maximum Matching: Towards a Parallel Algorithm

0 references

Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors

0 references

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors

0 references

Drawing trees with perfect angular resolution and polynomial area

0 references

Paths, Trees, and Flowers

0 references

Diameter and treewidth in minor-closed graph families

0 references

Succinct Greedy Geometric Routing Using Hyperbolic Geometry

0 references

Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time

0 references

On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching

0 references

Bipartite Perfect Matching in Pseudo-Deterministic NC

0 references

Linear matroid intersection is in quasi-NC

0 references

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

0 references

Characterizing multiterminal flow networks and computing flows in networks of small treewidth

0 references

Fast Algorithms for Finding Nearest Common Ancestors

0 references

Parallel Algorithms in Graph Theory: Planarity Testing

0 references

Random generation of combinatorial structures from a uniform distribution

0 references

\textsc{max-cut} and containment relations in graphs

0 references

Constructing a perfect matching is in random NC

0 references

Q5605168

0 references

On mimicking networks representing minimum terminal cuts

0 references

Mimicking Networks and Succinct Representations of Terminal Cuts

0 references

Q5414566

0 references

Q4097310

0 references

Q3891767

0 references

A Simple Parallel Algorithm for the Maximal Independent Set Problem

0 references

A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)

0 references

An excluded minor theorem for the Octahedron plus an edge

0 references

The structure of graphs not topologically containing the Wagner graph

0 references

Flow in Planar Graphs with Multiple Sources and Sinks

0 references

Matching is as easy as matrix inversion

0 references

Optimization and Recognition for K 5-minor Free Graphs in Linear Time

0 references

Undirected ST-connectivity in log-space

0 references

Q4273877

0 references

NC Algorithms for Weighted Planar Perfect Matching and Related Problems

0 references

A data structure for dynamic trees

0 references

Counting the number of perfect matchings in \(K_{5}\)-free graphs

0 references

An Efficient Parallel Biconnectivity Algorithm

0 references

The complexity of computing the permanent

0 references

NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems

0 references

Über eine Eigenschaft der ebenen Komplexe

0 references

Identifiers

zbMATH Open document ID

1466.05179

0 references

DOI

10.1137/19M1256221

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4994988

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.00084
@@ Property / arXiv ID: 1802.00084 / rank @@
+Normal rank
@@ Property / cites work @@
+Planar Graph Perfect Matching Is in NC
@@ Property / cites work: Planar Graph Perfect Matching Is in NC / rank @@
+Normal rank
@@ Property / cites work @@
+An approach to the subgraph homeomorphism problem
@@ Property / cites work: An approach to the subgraph homeomorphism problem / rank @@
+Normal rank
@@ Property / cites work @@
+All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
+Normal rank
@@ Property / cites work @@
+Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
+Normal rank
@@ Property / cites work @@
+Flows in One-Crossing-Minor-Free Graphs
@@ Property / cites work: Flows in One-Crossing-Minor-Free Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Computing mimicking networks
@@ Property / cites work: Computing mimicking networks / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Parallel Matrix Inversion Algorithms
@@ Property / cites work: Fast Parallel Matrix Inversion Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Planar Maximum Matching: Towards a Parallel Algorithm
+Normal rank
@@ Property / cites work @@
+Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
+Normal rank
@@ Property / cites work @@
+Drawing trees with perfect angular resolution and polynomial area
+Normal rank
@@ Property / cites work @@
+Paths, Trees, and Flowers
@@ Property / cites work: Paths, Trees, and Flowers / rank @@
+Normal rank
@@ Property / cites work @@
+Diameter and treewidth in minor-closed graph families
+Normal rank
@@ Property / cites work @@
+Succinct Greedy Geometric Routing Using Hyperbolic Geometry
+Normal rank
@@ Property / cites work @@
+Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
+Normal rank
@@ Property / cites work @@
+On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
+Normal rank
@@ Property / cites work @@
+Bipartite Perfect Matching in Pseudo-Deterministic NC
+Normal rank
@@ Property / cites work @@
+Linear matroid intersection is in quasi-NC
@@ Property / cites work: Linear matroid intersection is in quasi-NC / rank @@
+Normal rank
@@ Property / cites work @@
+Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
+Normal rank
@@ Property / cites work @@
+Characterizing multiterminal flow networks and computing flows in networks of small treewidth
+Normal rank
@@ Property / cites work @@
+Fast Algorithms for Finding Nearest Common Ancestors
+Normal rank
@@ Property / cites work @@
+Parallel Algorithms in Graph Theory: Planarity Testing
+Normal rank
@@ Property / cites work @@
+Random generation of combinatorial structures from a uniform distribution
+Normal rank
@@ Property / cites work @@
+\textsc{max-cut} and containment relations in graphs
+Normal rank
@@ Property / cites work @@
+Constructing a perfect matching is in random NC
@@ Property / cites work: Constructing a perfect matching is in random NC / rank @@
+Normal rank
@@ Property / cites work @@
+Q5605168
@@ Property / cites work: Q5605168 / rank @@
+Normal rank
@@ Property / cites work @@
+On mimicking networks representing minimum terminal cuts
+Normal rank
@@ Property / cites work @@
+Mimicking Networks and Succinct Representations of Terminal Cuts
+Normal rank
@@ Property / cites work @@
+Q5414566
@@ Property / cites work: Q5414566 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4097310
@@ Property / cites work: Q4097310 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3891767
@@ Property / cites work: Q3891767 / rank @@
+Normal rank
@@ Property / cites work @@
+A Simple Parallel Algorithm for the Maximal Independent Set Problem
+Normal rank
@@ Property / cites work @@
+A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
+Normal rank
@@ Property / cites work @@
+An excluded minor theorem for the Octahedron plus an edge
+Normal rank
@@ Property / cites work @@
+The structure of graphs not topologically containing the Wagner graph
+Normal rank
@@ Property / cites work @@
+Flow in Planar Graphs with Multiple Sources and Sinks
+Normal rank
@@ Property / cites work @@
+Matching is as easy as matrix inversion
@@ Property / cites work: Matching is as easy as matrix inversion / rank @@
+Normal rank
@@ Property / cites work @@
+Optimization and Recognition for K 5-minor Free Graphs in Linear Time
+Normal rank
@@ Property / cites work @@
+Undirected ST-connectivity in log-space
@@ Property / cites work: Undirected ST-connectivity in log-space / rank @@
+Normal rank
@@ Property / cites work @@
+Q4273877
@@ Property / cites work: Q4273877 / rank @@
+Normal rank
@@ Property / cites work @@
+NC Algorithms for Weighted Planar Perfect Matching and Related Problems
+Normal rank
@@ Property / cites work @@
+A data structure for dynamic trees
@@ Property / cites work: A data structure for dynamic trees / rank @@
+Normal rank
@@ Property / cites work @@
+Counting the number of perfect matchings in \(K_{5}\)-free graphs
+Normal rank
@@ Property / cites work @@
+An Efficient Parallel Biconnectivity Algorithm
@@ Property / cites work: An Efficient Parallel Biconnectivity Algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+Normal rank
@@ Property / cites work @@
+NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
+Normal rank
@@ Property / cites work @@
+Über eine Eigenschaft der ebenen Komplexe
@@ Property / cites work: Über eine Eigenschaft der ebenen Komplexe / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W3166103872
@@ Property / OpenAlex ID: W3166103872 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:4994988