The computational complexity of graph problems with succinct multigraph representation

DOI10.1007/BF01928922zbMath0655.05063MaRDI QIDQ3801600

Marek Karpinski, Klaus W. Wagner

Publication date: 1988

Published in: Zeitschrift für Operations Research (Search for Journal in Brave)

zbMATH Keywords

complexitymatchinggraph algorithmssuccinct presentationvertex multiplicity graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99)

Related Items (4)

Languages represented by Boolean formulas ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Succinct representation, leaf languages, and projection reductions ⋮ On the complexity of data disjunctions.

Cites Work

• Unnamed Item
• The binary network flow problem is logspace complete for P
• Matching is as easy as matrix inversion
• Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
• Geometric algorithms and combinatorial optimization
• Succinct representations of graphs
• A taxonomy of problems with fast parallel algorithms
• A note on succinct representations of graphs

This page was built for publication: The computational complexity of graph problems with succinct multigraph representation