Set graphs. II. Complexity of set graph recognition and similar problems
DOI10.1016/j.tcs.2014.06.017zbMath1298.05146arXiv1207.7184MaRDI QIDQ2253199
Alexandru I. Tomescu, Martin Milanič, Romeo Rizzi
Publication date: 25 July 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.7184
extensionality; acyclic orientation; NP-complete problem; separating code; set graph; \#P-complete problem; hyper-extensional digraph; open-out-separating code
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C20: Directed graphs (digraphs), tournaments
05C62: Graph representations (geometric and intersection representations, etc.)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Set graphs. IV. Further connections with claw-freeness
- Open neighborhood locating-dominating in trees
- Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
- CCS expressions, finite state processes, and three problems of equivalence
- Discriminating codes in (bipartite) planar graphs
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Approximation algorithms for the test cover problem
- An efficient algorithm for computing bisimulation equivalence
- Set graphs. I. Hereditarily finite sets and extensional acyclic orientations
- Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
- Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
- Induced subsets
- Well-quasi-ordering hereditarily finite sets
- {log}: A language for programming in logic with finite sets
- Discriminating codes in bipartite graphs
- Three Partition Refinement Algorithms
- Approximately Counting Hamilton Paths and Cycles in Dense Graphs
- On a new class of codes for identifying vertices in graphs
- Identifying and locating-dominating codes: NP-completeness results for directed graphs
- Computational Logic and Set Theory
