The Linkage of a Graph

DOI10.1137/S0097539793255709MaRDI QIDQ4887020zbMATH OpenDBLPWikidataFDO

Authors L. M. Kirousis, Dimitrios M. Thilikos

Publication date 15 October 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

constraint satisfaction problemsbacktrack-free searchlinkage of a graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Recommendations

• Graph minors. XXI. graphs with unique linkages
• DAG-width and circumference of digraphs
• The directed 2-linkage problem with length constraints
• Parameterized and Exact Computation
• Disjoint paths in decomposable digraphs

Cited in

(11)

• The equivalence chain of a graph
• Fugitive-search games on graphs and related parameters
• Treewidth for graphs with small chordality
• Online promise problems with online width metrics
• Graph-links
• Fugitive-search games on graphs and related parameters
• On the monotonicity of games generated by symmetric submodular functions.
• Linkages in Polytope Graphs
• The Strong Linkage Principle
• Edge degeneracy: algorithmic and structural results
• Why is maximum clique often easy in practice?

This page was built for publication: The Linkage of a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4887020)