NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs

No abstract is available for this paper.

• Publication year

  2018

• Venue

  arXiv.org

• Publication date

  2018-01-31

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

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

  2018cited by this paper
• Linear Matroid Intersection is in Quasi-NC

  2017cited by this paper
• Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

  2017cited by this paper
• Planar Graph Perfect Matching Is in NC

  2017influential reference
• The Matching Problem in General Graphs Is in Quasi-NC

  2017cited by this paper
• Bipartite perfect matching is in quasi-NC

  2016cited by this paper
• On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching

  2016cited by this paper
• All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

  2014cited by this paper
• On mimicking networks representing minimum terminal cuts

  2012cited by this paper
• Mimicking Networks and Succinct Representations of Terminal Cuts

  2012cited by this paper
• An Efficient Parallel Biconnectivity Algorithm

  2011cited by this paper
• Succinct Greedy Geometric Routing Using Hyperbolic Geometry

  2011cited by this paper
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

  2011cited by this paper
• Drawing Trees with Perfect Angular Resolution and Polynomial Area

  2010cited by this paper
• Logspace Versions of the Theorems of Bodlaender and Courcelle

  2010cited by this paper
• Optimization and Recognition for K 5-minor Free Graphs in Linear Time

  2008cited by this paper
• A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)

  2000cited by this paper
• Computing Mimicking Networks

  1998cited by this paper
• Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth

  1998influential reference
• Excluding a graph with one crossing

  1991cited by this paper
• NC Algorithms for Computing the Number of Perfect Matchings in K_3,3-Free Graphs and Related Problems

  1989cited by this paper
• Flow in planar graphs with multiple sources and sinks

  1989cited by this paper
• NC Algorithms for Computing the Number of Perfect Matchings in K3, 3-free Graphs and Related Problems

  1988cited by this paper
• Matching is as easy as matrix inversion

  1987cited by this paper
• A simple parallel algorithm for the maximal independent set problem

  1985cited by this paper
• An Approach to the Subgraph Homeomorphism Problem

  1985cited by this paper
• Constructing a perfect matching is in random NC

  1985cited by this paper
• Are search and decision programs computationally equivalent?

  1985cited by this paper
• Fast Algorithms for Finding Nearest Common Ancestors

  1984cited by this paper
• Parallel Algorithms in Graph Theory: Planarity Testing

  1982cited by this paper
• Parallel algorithms for minimum cuts and maximum flows in planar networks

  1982influential reference
• A data structure for dynamic trees

  1981cited by this paper
• On determinants, matchings, and random algorithms

  1979cited by this paper
• Fast parallel matrix inversion algorithms

  1975cited by this paper
• An Extension of kasteleyn's method of enumerating the 1-factors of planar graphs

  1974cited by this paper

• A Pseudo-Deterministic RNC Algorithm for General Graph Perfect Matching

  2019cites this paper
• A deterministic parallel algorithm for bipartite perfect matching

  2019cites this paper
• Matching Is as Easy as the Decision Problem, in the NC Model

  2019cites this paper
• N ov 2 01 9 Channels , Billiards , and Perfect Matching 2-Divisibility

  2019cites this paper
• Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time

  2018cites this paper
• Planar Maximum Matching: Towards a Parallel Algorithm

  2018cites this paper
• Planar Graph Perfect Matching Is in NC

  2017cites this paper